{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python程序设计基础及实践(慕课版)教材题集参考答案\n",
    "\n",
    "习题链接:\n",
    "http://cxsjsxmooc.openjudge.cn/book/\n",
    "\n",
    "郭炜老师python mooc的题解，方法不唯一，仅供参考。\n",
    "\n",
    "如有错漏敬请指正。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 001:A+B问题\n",
    "描述:\n",
    "在一行输入两个整数，请输出它们的和。\n",
    "\n",
    "输入:\n",
    "一行，两个整数。\n",
    "\n",
    "输出:\n",
    "两个整数的和。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a,b=map(int,input().split())\n",
    "print(a+b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "堪比Hello World的入门题目A+B问题，会读入两个整数就行。当然，你也可以写两个int()类型转换；上面的写法是oj上做题最常用的读入方式。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 002:字符三角形\n",
    "描述:\n",
    "给定一个字符，用它构造一个底边长5个字符，高3个字符的等腰字符三角形。\n",
    "\n",
    "输入:\n",
    "输入只有一行， 包含一个字符。\n",
    "\n",
    "输出:\n",
    "该字符构成的等腰三角形，底边长5个字符，高3个字符。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c=input()\n",
    "print(\" \",c,\" \")\n",
    "print(\" \",c,c,c,\" \",sep=\"\")\n",
    "print(c,c,c,c,c,sep=\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "最最淳朴的做法，考察print函数的sep与end参数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c=input()\n",
    "print(\" \",c,\" \")\n",
    "print(\"\",c*3,\"\")\n",
    "print(c*5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "字符串是可以直接乘的，就不用笨笨的一个个打了。当然，也可以更进一步，多用一些格式化输出的内容，像是这样:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c=input()\n",
    "print('{:^5}'.format(c))\n",
    "print('{:^5}'.format(c*3))\n",
    "print('{:^5}'.format(c*5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里的意思是总长度为5，居中对齐，很契合题目的需求。\n",
    "\n",
    "格式化输出是很好用的东西，做题的时候也经常会遇到，要熟悉一下。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 003:计算(a+b)*c的值\n",
    "描述:\n",
    "给定3个整数a、b、c，计算表达式(a+b)*c的值。\n",
    "\n",
    "输入:\n",
    "输入仅一行，包括三个整数a、b、c, 数与数之间以一个空格分开。\n",
    "(－10,000 < a,b,c < 10,000)\n",
    "\n",
    "输出:\n",
    "输出一行，即表达式的值。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a,b,c=map(int,input().split())\n",
    "print((a+b)*c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "和第一题A+B可以说是完全一致了，没什么好说的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 004:反向输出一个三位数\n",
    "描述:\n",
    "将一个三位数反向输出。\n",
    "\n",
    "输入:\n",
    "一个三位数n。\n",
    "\n",
    "输出:\n",
    "反向输出n。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s=input()\n",
    "print(s[::-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "熟练掌握了字符串切片的用法就可以不用憨憨的一位位取出来了，好耶。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 005:字符菱形\n",
    "描述:\n",
    "给定一个字符，用它构造一个对角线长5个字符，倾斜放置的菱形。\n",
    "\n",
    "输入:\n",
    "输入只有一行， 包含一个字符。\n",
    "\n",
    "输出:\n",
    "该字符构成的菱形。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c=input()\n",
    "print('{:^5}'.format(c))\n",
    "print('{:^5}'.format(c*3))\n",
    "print('{:^5}'.format(c*5))\n",
    "print('{:^5}'.format(c*3))\n",
    "print('{:^5}'.format(c))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "和第二题的字符三角形完全一致。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 006:输出第二个整数\n",
    "描述:\n",
    "输入三个整数，把第二个输入的整数输出。\n",
    "\n",
    "输入:\n",
    "只有一行，共三个整数，整数之间由一个空格分隔。整数是32位有符号整数。\n",
    "\n",
    "输出:\n",
    "只有一行，一个整数，即输入的第二个整数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a,b,c=input().split()\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 007:求三个数的和\n",
    "描述:\n",
    "输入三个整数或小数，输出它们的和。\n",
    "\n",
    "- 如果结果是整数，就保留小数点后面一位的0(用python写则不用特别处理，程序自然会如此)    \n",
    "\n",
    "输入:\n",
    "输入三个整数或小数。\n",
    "\n",
    "输出:\n",
    "和。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a,b,c=map(float,input().split())\n",
    "print(a+b+c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 008:字符串交换\n",
    "描述:\n",
    "输入两个长度为4的字符串，交换这两个字符串的前两个字符后输出\n",
    "\n",
    "输入:\n",
    "两个长度为4的字符串\n",
    "\n",
    "输出:\n",
    "交换这两个字符串的前两个字符后输出"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s1=input()\n",
    "s2=input()\n",
    "print(s2[0:2]+s1[2:4])\n",
    "print(s1[0:2]+s2[2:4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "考察字符串的索引与切片，也没有必要修改两个字符串，直接输出结果就好了。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 009:字符串中的整数求和\n",
    "描述:\n",
    "输入两个长度为3的字符串，每个串前两个字符是数字,后一个字符是字母。 求这两个串中的整数的和\n",
    "\n",
    "输入:\n",
    "一行，两个字符串。\n",
    "\n",
    "输出:\n",
    "两个字符串中整数的和。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s1,s2=input().split()\n",
    "print(int(s1[0:2])+int(s2[0:2]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "哪些位置是数字都告诉你了，取出来之后做运算就好了。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 010:求(x+y)*x的值\n",
    "描述:\n",
    "在一行输入两个小数或整数x,y，请输出 (x+y)*x的值，保留小数点后面5位。\n",
    "\n",
    "输入:\n",
    "一行，两个小数或整数x,y。\n",
    "\n",
    "输出:\n",
    "(x+y)*x的值，保留小数点后面5位。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x,y=map(float,input().split())\n",
    "ans=(x+y)*x\n",
    "print(\"%.5f\"%ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "计算不难，主要考察格式化输出控制小数位数，在oj做题时格式化输出是非常重要的内容，再次强调一下。当然也有一些别的写法，如下:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x,y=map(float,input().split())\n",
    "ans=(x+y)*x\n",
    "print(\"{:.5f}\".format(ans))\n",
    "print(f\"{ans:.5f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 011:奇偶数判断\n",
    "\n",
    "描述:\n",
    "给定一个整数，判断该数是奇数还是偶数。\n",
    "\n",
    "输入:\n",
    "输入仅一行，一个大于零的正整数n。\n",
    "\n",
    "输出:\n",
    "输出仅一行，如果n是奇数，输出odd；如果n是偶数，输出even。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=int(input())\n",
    "print('odd' if n % 2 else 'even')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果条件满足则值为前者，否则为后者。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 012:判断子串\n",
    "\n",
    "描述:\n",
    "输入两行字符串，要求判断第一行 字符串是不是第二行的子串  \n",
    "\n",
    "输入:\n",
    "两行字符串。字符串长度不超过100。\n",
    "\n",
    "输出:\n",
    "如果第一行是第二行的子串，就输出 \"YES\"，否则输出\"NO\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "str1=input()\n",
    "str2=input()\n",
    "print('YES' if str1 in str2 else 'NO')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 013:三角形判断\n",
    "\n",
    "描述:\n",
    "给定三个正整数，分别表示三条线段的长度，判断这三条线段能否构成一个三角形。\n",
    "\n",
    "输入:\n",
    "输入共一行，包含三个正整数，分别表示三条线段的长度，数与数之间以一个空格分开。\n",
    "\n",
    "输出:\n",
    "如果能构成三角形，则输出“yes” ，否则输出“no”。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lst=list(map(int,input().split()))\n",
    "lst.sort()\n",
    "print('yes' if lst[0]+lst[1]>lst[2] else 'no')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "三角形较短两边之和要大于第三边，先对线段长度进行排序后即可避免冗长的分类讨论，当然也可以直接进行判断。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 014:简单计算器\n",
    "\n",
    "描述:\n",
    "一个最简单的计算器，支持+, -, *, / 四种运算。仅需考虑输入输出为整数的情况(除法结果就是商，忽略余数）\n",
    "\n",
    "输入:\n",
    "输入只有一行，共有三个参数，其中第1、2个参数为整数，第3个参数为操作符（+,-,*,/）。\n",
    "\n",
    "输出:\n",
    "输出只有一行，一个整数，为运算结果。然而：\n",
    "1. 如果出现除数为0的情况，则输出：Divided by zero!\n",
    "2. 如果出现无效的操作符(即不为 +, -, *, / 之一），则输出：Invalid operator!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lst=input().split()\n",
    "if lst[2] not in '+-*/':\n",
    "    print('Invalid operator!')\n",
    "elif lst[2]=='/' and lst[1]=='0':\n",
    "    print('Divided by zero!')\n",
    "else:\n",
    "    print(int(eval(lst[0]+lst[2]+lst[1])))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "判断特殊情况后直接利用eval()函数，取巧的写法；当然也可以用if语句按照四种运算进行考虑。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 015:摄氏华氏温度转换\n",
    "\n",
    "描述:\n",
    "输入摄氏温度，就将其转换为华氏温度输出；输入华氏温度，就将其转换成摄氏温度数输出。两者的转换关系是：\n",
    "\n",
    "摄氏温度 =（华氏温度 - 32 ) ÷ 1.8\n",
    "\n",
    "输入:\n",
    "摄氏温度或华氏温度。摄氏温度的格式是一个整数或小数后面加'C'或'c'，华氏温度的格式是一个整数或小数后面加'F'或'f'。\n",
    "\n",
    "输出:\n",
    "转换后的温度。摄氏温度就在数值后面加'C'，华氏温度就在数值后面加'F'。如果数值是整数，就应该输出整数形式，如果数值是小数，则保留小数点后面2位。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "eps=1e-6\n",
    "\n",
    "x=input()\n",
    "if x[-1]==\"f\" or x[-1]==\"F\":    #或者写成:if x[-1] in 'fF'\n",
    "    t=(eval(x[:-1])-32)/1.8\n",
    "    s=\"C\"\n",
    "else:    \n",
    "    t=eval(x[:-1])*1.8+32\n",
    "    s=\"F\"\n",
    "if abs(t-round(t))<eps:\n",
    "    print(f'{t:.0f}'+s)\n",
    "else:\n",
    "    print(f'{t:.2f}'+s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "到目前为止比较综合的一道题。\n",
    "\n",
    "注意要区分输出的整数还是小数以确定输出格式，但由于进行的是浮点运算，所以会有误差，确定整数不能用\n",
    "\n",
    "`round(x)==x` 而是 `abs(x-round(x))<eps`。\n",
    "\n",
    "这里的eps定义为一个极小的数，也就是折磨大家高数的epsilon——$\\epsilon$。\n",
    "\n",
    "捎带一提关于浮点运算的误差，之前也学到了数据在计算机中的存储与表示，浮点数表示带来的误差导致了下面的错误结果。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(0.1+0.2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 016:幸运的年份\n",
    "\n",
    "描述:\n",
    "输入一个年份，如果该年份是建国整十周年，就输出\"Lucky year\"；如果是建党整十周年，就输出\"Good year\"；如果是闰年，就输出\"Leap year\"；如果是大于0的其它年份，就输出\"Common year\"。如果输入的年份小于0，则输出\"Illegal year\"。\n",
    "\n",
    "闰年的定义是：能被400整除的年份，或能被4整除，但不能被100整除的年份。\n",
    "\n",
    "输入:\n",
    "一个整数，代表年份。\n",
    "\n",
    "输出:\n",
    "按要求输出。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "isleap=lambda x:x%400==0 or (x%4==0 and x%100)\n",
    "isnation=lambda x:x>1949 and x%10==9\n",
    "isparty=lambda x:x>1921 and x%10==1\n",
    "\n",
    "x=int(input())\n",
    "if x<0:\n",
    "    print('Illegal year')\n",
    "elif isleap(x):\n",
    "    print('Leap year')\n",
    "elif isnation(x):\n",
    "    print('Lucky year')\n",
    "elif isparty(x):\n",
    "    print('Good year')\n",
    "else:\n",
    "    print('Common year')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "同上题，lambda 部分可以直接移到判断里而不定义函数，没有什么好注意的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 017:计算2的幂\n",
    "\n",
    "描述:\n",
    "给定非负整数n，求 $2^n$。\n",
    "\n",
    "输入:\n",
    "一个整数n。0 <= n < 31。\n",
    "\n",
    "输出:\n",
    "一个整数，即2的n次方。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=int(input())\n",
    "print(2**n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "不是很理解这题的目的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 018:计算多项式的值\n",
    "\n",
    "描述:\n",
    "对于多项式f(x) = ax3 + bx2 + cx + d 和给定的a, b, c, d, x，计算f(x)的值。\n",
    "\n",
    "输入:\n",
    "输入仅一行，包含5个实数，分别是x，及参数a、b、c、d的值，每个数都是绝对值不超过100的双精度浮点数。数与数之间以一个空格分开。\n",
    "\n",
    "输出:\n",
    "输出一个实数，即f(x)的值，保留到小数点后7位。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x,a,b,c,d=map(eval,input().split())\n",
    "print(f'{a*x**3+b*x**2+c*x+d:.7f}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "也可以不用 map,但不是那么好看"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x,a,b,c,d=input().split()\n",
    "print(f'{eval(f\"{a}*{x}**3+{b}*{x}**2+{c}*{x}+{d}\"):.7f}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 019:车牌限号\n",
    "\n",
    "描述:\n",
    "今天某市交通管制，车牌尾号为奇数的车才能上路。问给定的车牌号今天是否能上路。\n",
    "\n",
    "输入:\n",
    "一行。一个由字母和数字构成的长度为1到10的字符串，代表车牌号，车牌号最后一位是数字。\n",
    "\n",
    "输出:\n",
    "今天可以上路，输出“YES”，否则输出“NO”。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x=input()\n",
    "print('YES' if int(x[-1])%2 else 'NO')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "没啥好说的，奇偶数判断的应用版"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 020:点和正方形的关系\n",
    "\n",
    "描述:\n",
    "有一个正方形，四个角的坐标（x,y) 分别是（1，-1），（1，1），（-1，-1），（-1，1），x是横轴，y是纵轴。写一个程序，判断一个给定的点是否在这个正方形内（包括正方形边界）。\n",
    "\n",
    "输入:\n",
    "输入一行，包括两个整数x、y，以一个空格分开，表示坐标(x,y)。\n",
    "\n",
    "输出:\n",
    "输出一行，如果点在正方形内，则输出yes，否则输出no。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "isin=lambda x,y:x**2<=1 and y**2<=1\n",
    "\n",
    "x,y=map(int,input().split())\n",
    "print('yes' if isin(x,y) else 'no')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "没啥好说的，平方改成大于等于-1小于等于1也可以"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 021:计算邮资\n",
    "\n",
    "描述:\n",
    "根据邮件的重量和用户是否选择加急计算邮费。计算规则：重量在1000克以内(包括1000克), 基本费8元。超过1000克的部分，每500克加收超重费4元，不足500克部分按500克计算；如果用户选择加急，多收5元。\n",
    "\n",
    "输入:\n",
    "输入一行，包含整数和一个字符，以一个空格分开，分别表示重量（单位为克）和是否加急。如果字符是y，说明选择加急；如果字符是n，说明不加急。\n",
    "\n",
    "输出:\n",
    "输出一行，包含一个整数，表示邮费。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import ceil\n",
    "\n",
    "n,c=input().split()\n",
    "n=int(n)\n",
    "sum=(0 if c=='n' else 5)\n",
    "if n<=500:\n",
    "    sum+=4\n",
    "sum+=ceil(n/500)*4\n",
    "print(sum)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "简单的分段函数，考虑到可读性建议采用分段 if 来写，我只是单纯不喜欢写分支所以这么写了，但是不建议"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import ceil\n",
    "\n",
    "n,c=input().split()\n",
    "n=int(n)\n",
    "sum=(0 if c=='n' else 5)\n",
    "if n<=1000:\n",
    "    sum+=8\n",
    "else:\n",
    "    sum+=ceil(n/500)*4\n",
    "print(sum)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "说不喜欢最后还是写了"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 022:分段函数\n",
    "\n",
    "描述:\n",
    "编写程序，计算下列分段函数y=f(x)的值。\n",
    "$$\n",
    "y=-x+2.5; 0 \\le x < 5\n",
    "\\\\\n",
    "y=2-1.5(x-3)(x-3); 5 \\le x < 10\n",
    "\\\\\n",
    "y=x/2-1.5; 10 \\le x < 20\n",
    "$$\n",
    "\n",
    "输入:\n",
    "一个浮点数N,0 <= N < 20\n",
    "\n",
    "输出:\n",
    "输出N对应的分段函数值：f(N)。结果保留到小数点后三位。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def y(x):\n",
    "    if 0<=x<5:\n",
    "        return -x+2.5\n",
    "    elif 5<=x<10:\n",
    "        return 2-1.5*(x-3)**2\n",
    "    elif 10<=x<20:\n",
    "        return x/2-1.5\n",
    "\n",
    "N=eval(input())\n",
    "print(f'{y(N):.3f}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "没啥好讲的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 023:大象喝水\n",
    "\n",
    "描述:\n",
    "一只大象口渴了，要喝20升水才能解渴，但现在只有一个深h厘米，底面半径为r厘米的小圆桶(h和r都是整数)。问大象至少要喝多少桶水才会解渴。\n",
    "\n",
    "输入:\n",
    "输入有一行：包行两个整数，以一个空格分开，分别表示小圆桶的深h和底面半径r，单位都是厘米。\n",
    "\n",
    "输出:\n",
    "输出一行，包含一个整数，表示大象至少要喝水的桶数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import ceil\n",
    "\n",
    "pi=3.14159\n",
    "\n",
    "h,r=map(int,input().split())\n",
    "print(ceil(20000/(pi*r**2*h)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "没啥好讲的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 024:苹果和虫子2\n",
    "\n",
    "描述:\n",
    "你买了一箱n个苹果，很不幸的是买完时箱子里混进了一条虫子。虫子每x小时能吃掉一个苹果，假设虫子在吃完一个苹果之前不会吃另一个，那么经过y小时你还有多少个完整的苹果？\n",
    "\n",
    "输入:\n",
    "输入仅一行，包括n，x和y（均为整数）。\n",
    "\n",
    "输出:\n",
    "输出也仅一行，剩下的苹果个数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import ceil\n",
    "\n",
    "n,x,y=map(int,input().split())\n",
    "print(n-ceil(y/x) if y<n*x else 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注意不要忽略吃完的情况，剩下的完整苹果不会是负数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 025:求一元二次方程的根\n",
    "\n",
    "描述:\n",
    "利用公式x1 = (-b + sqrt(b* b-4* a* c))/(2* a), x2 = (-b - sqrt(b* b-4* a* c))/(2* a)求一元二次方程ax^2+ bx + c =0的根，其中a不等于0。\n",
    "\n",
    "输入:\n",
    "输入一行，包含三个浮点数a, b, c（它们之间以一个空格分开），分别表示方程ax2 + bx + c =0的系数。\n",
    "\n",
    "输出:\n",
    "输出一行，表示方程的解。\n",
    "\n",
    "若b2 = 4 * a * c,则两个实根相等，则输出形式为：x1=x2=...。\n",
    "\n",
    "若b2 > 4 * a * c,则两个实根不等，则输出形式为：x1=...;x2 = ...，其中x1>x2。\n",
    "\n",
    "若b2 < 4 * a * c，则有两个虚根，则输出：x1=实部+虚部i; x2=实部-虚部i，即x1的虚部系数大于等于x2的虚部系数，实部为0时不可省略。实部 = -b / (2*a), 虚部 = sqrt(4*a*c-b*b) / (2*a)\n",
    "\n",
    "所有实数部分要求精确到小数点后5位，数字、符号之间没有空格。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from cmath import sqrt\n",
    "\n",
    "a,b,c = map(float,input().split())\n",
    "delta=b**2-4*a*c\n",
    "x1=(-b+sqrt(delta))/(2*a)\n",
    "x2=(-b-sqrt(delta))/(2*a)\n",
    "if delta==0:\n",
    "    print(f'x1=x2={x1.real:.5f}')\n",
    "elif delta>0:\n",
    "    print(f'x1={x1.real:.5f};x2={x2.real:.5f}')\n",
    "else:\n",
    "    print(f'x1={x1:.5f};x2={x1.conjugate():.5f}'.replace('j','i'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "求解一元二次方程很自然的想到 python 内置的复数，所以只需要根据求根公式求出根以复数类型存储，而不需要讨论判别式的正负性\n",
    "\n",
    "math 里的 sqrt 只能对浮点数求平方根 所以用 cmath （complex) 中的sqrt\n",
    "\n",
    "题目要求的输出是用 i 表示虚数，所以格式化字符串之后用 replace 方法把 j 替换成 i\n",
    "\n",
    "捎带一提，如果根的实部为0，在 x2 会出现 x2.real=-0.00000 的情况，考虑到当判别式小于 0 的时候 x1 x2 互为共轭复数，所以用 x1.conjugate() 替代 x2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 026:输入 n 个整数求和\n",
    "\n",
    "描述:\n",
    "输入n个整数求和\n",
    "\n",
    "输入:\n",
    "第一行是整数n, n>= 1。后面有n行，每行一个整数。\n",
    "\n",
    "输出:\n",
    "输出后面那n个整数的和。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=int(input())\n",
    "sum=0\n",
    "for _ in range(n):\n",
    "    sum+=(int(input())) \n",
    "print(sum)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "稍微提一下，无用的变量可以在前面加下划线表示"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 027:从小到大输出正整数 n 的因子\n",
    "\n",
    "描述:\n",
    "给一个正整数n，从小到大输出n的因子\n",
    "\n",
    "输入:\n",
    "一个正整数,n\n",
    "\n",
    "输出:\n",
    "在一行中从小到大输出n的因子"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=int(input())\n",
    "lst,i=[],1\n",
    "while i*i<n:\n",
    "    if not n%i:\n",
    "        print(i,end=' ')\n",
    "        lst.append(int(n/i))\n",
    "    i+=1\n",
    "if i*i==n:\n",
    "    lst.append(i)    \n",
    "for item in lst[::-1]:\n",
    "    print(item,end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注意复杂度的问题，枚举到根号 n 为止，若能整除，将小的直接输出，并除出大的存入列表\n",
    "\n",
    "根号 n 是否为整数讨论\n",
    "\n",
    "列表此时是从大到小的，所以要倒置输出"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 028:多次求n个数的和\n",
    "\n",
    "描述:\n",
    "多次求n个数的和\n",
    "\n",
    "输入:\n",
    "第一行是整数m，m>=1,表示有m组数据。接下来就是m组数据。\n",
    "\n",
    "每组数据，第一行是整数n，n>= 1，表示有n个整数需要求和。接下来是n行，每行一个整数。\n",
    "\n",
    "输出:\n",
    "对每组数据，输出n个整数的和。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=int(input())\n",
    "for _1 in range(n):\n",
    "    m,sum=int(input()),0\n",
    "    for _2 in range(m):\n",
    "        sum+=int(input())\n",
    "    print(sum)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "套了两层循环\n",
    "别忘记每次求和把sum归零"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 029:字符直角三角形\n",
    "\n",
    "描述:\n",
    "输入一个字符c和一个整数n(n>0)，要求输出一个高为n行的由字符c构成的直角三角形，第i行有i个字符c。\n",
    "\n",
    "输入:\n",
    "一行，包括字符c和整数n\n",
    "\n",
    "输出:\n",
    "一个高为n行的由字符c构成的直角三角形，第i行有i个字符c。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "c,n=input().split()\n",
    "for i in range(1,int(n)+1):\n",
    "    print(c*i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "没啥好说的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 030:多少种和为因子的取法\n",
    "\n",
    "描述:\n",
    "输入正整数n和m,在1至n这n个整数中，取出两个不同的数，使得其和是m的因子，问有多少种不同的取法。输出这些取法。\n",
    "\n",
    "数据规模很小的简单枚举题，不用考虑怎么算快。\n",
    "\n",
    "输入:\n",
    "一行，正整数n和m。n和m都不大，不必担心超时\n",
    "\n",
    "输出:\n",
    "每种取法由2个数表示，第一个数必须小于第二个数。按第一个数从小到大的顺序，输出所有取法。每行一种取法。最后一行输出取法总数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import combinations\n",
    "\n",
    "n,m=map(int,input().split())\n",
    "count=0\n",
    "n_list=range(1,n+1)\n",
    "n2_list=combinations(n_list,2)\n",
    "for item in n2_list:\n",
    "    if not m%sum(item):\n",
    "        print(f'{item[0]} {item[1]}')\n",
    "        count+=1\n",
    "print(count)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面是采用 combinations 的做法，当然也可以两重循环枚举"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n,m=map(int,input().split())\n",
    "count=0\n",
    "for i in range(1,n+1):\n",
    "    for j in range(i+1,n+1):\n",
    "        if not m%(i+j):\n",
    "            print(f'{i} {j}')\n",
    "            count+=1\n",
    "print(count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 031:寻找子串\n",
    "\n",
    "描述:\n",
    "字符串s1由小写字母构成，字符串s2由小写字母和空格构成。字符串s3是s2去掉空格以后形成的字符串，求s3在s1中的第一次出现的位置。\n",
    "\n",
    "输入:\n",
    "第一行是字符串s1，第二行是字符串s2。s1、s2长度都不超过100。\n",
    "\n",
    "输出:\n",
    "s3在s1中首次出现的位置。位置即下标，从0开始算。如果没有出现，则输出-1。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s1=input()\n",
    "s3=input().replace(' ','')\n",
    "print(s1.find(s3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "字符串的一些处理\n",
    "\n",
    "删去、替换掉字符串中的特定字符可以采用 replace 方法\n",
    "\n",
    "寻找子串位置可以用 find 方法\n",
    "\n",
    "具体说明 help 或者搜索引擎"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 032:求最小公倍数\n",
    "\n",
    "描述:\n",
    "输入三个不超过100的正整数，求它们的最小公倍数。\n",
    "\n",
    "输入:\n",
    "一行，三个不超过100的正整数\n",
    "\n",
    "输出:\n",
    "三个整数的最小公倍数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们先考虑一下两个数的最小公倍数怎么求（当然你可以从小到大枚举）\n",
    "\n",
    "实际上，两数相乘 = 最大公因数(gcd) * 最小公倍数(lcm)\n",
    "\n",
    "所以我们只要求出最大公因数就可以了\n",
    "\n",
    "而求最大公因数可以用辗转相除法递归(没听说过的话可以直接搜)\n",
    "\n",
    "然后三个数的最小公倍数只需要求出前两数最小公倍数再求和第三数的最小公倍数就行了"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gcd(a,b):\n",
    "    if not a%b:\n",
    "        return b\n",
    "    return gcd(b,a%b)\n",
    "\n",
    "def lcm(a,b):\n",
    "    return int(a*b/gcd(a,b))\n",
    "\n",
    "a,b,c=map(int,input().split())\n",
    "print(lcm(lcm(a,b),c))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "顺便补一个枚举的"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a,b,c=map(int,input().split())\n",
    "m=n=max(a,b,c)\n",
    "while n%a or n%b or n%c:\n",
    "    n+=m\n",
    "print(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "效率低了很多，oj上提交比比看就知道了\n",
    "\n",
    "下面讨论一下有 n 个数，即求一个列表的最小公倍数\n",
    "\n",
    "先试着递归"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gcd(a,b):\n",
    "    if not a%b:\n",
    "        return b\n",
    "    return gcd(b,a%b)\n",
    "\n",
    "def lcm(a,b):\n",
    "    return int(a*b/gcd(a,b))\n",
    "\n",
    "def listlcm(lst):\n",
    "    if len(lst)==2:\n",
    "        return lcm(lst[0],lst[1])\n",
    "    return lcm(listlcm(lst[:-1]),lst[-1])\n",
    "\n",
    "lst=list(map(int,input().split()))\n",
    "print(listlcm(lst))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "总的来说，递归还挺有用的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 033:十进制数转二进制数\n",
    "\n",
    "描述:\n",
    "输入一个十进制形式整数，请输出其二进制表示形式。\n",
    "\n",
    "输入:\n",
    "一个十进制形式整数\n",
    "\n",
    "输出:\n",
    "请输出其二进制表示形式"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=int(input())\n",
    "print(f'{n:b}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "没啥好讲的\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "我开玩笑的，正经用循环来写短除"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sig,ans='',''\n",
    "n=int(input())\n",
    "if n<0:\n",
    "    sig='-'\n",
    "    n=-n\n",
    "elif n==0:\n",
    "    ans='0'\n",
    "while n:\n",
    "    ans=str(n%2)+ans\n",
    "    n//=2\n",
    "print(sig+ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 034：求最大整数\n",
    "\n",
    "描述:\n",
    "求若干整数中最大的那个\n",
    "\n",
    "输入:\n",
    "若干行，每行若干整数。\n",
    "\n",
    "输出:\n",
    "所有整数中最大的那个。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "final_list = []\n",
    "while True:\n",
    "    try:\n",
    "        input_list = map(int,input().split())\n",
    "        final_list.extend(input_list)\n",
    "    except:\n",
    "        break\n",
    "print(max(final_list))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "因为无法确定输入的量，所以采用异常处理来决定读入数据结束"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 035:求斐波那契数列第k项\n",
    "\n",
    "描述:\n",
    "菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。给出一个正整数k，要求菲波那契数列中第k个数是多少。\n",
    "\n",
    "输入:\n",
    "输入一行，包含一个正整数k（1<=k<=46）。\n",
    "\n",
    "输出:\n",
    "输出一行，包含一个正整数，表示菲波那契数列中第k个数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibonacci(k):\n",
    "    if k<3:\n",
    "        return 1\n",
    "    return fibonacci(k-2)+fibonacci(k-1)\n",
    "\n",
    "k=int(input())\n",
    "print(fibonacci(k))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面的是最基本的递归写法\n",
    "\n",
    "但是提交到 Oj 上炸了\n",
    "\n",
    "这是因为递归的时候每次调用函数，都要重复计算一次，累加起来复杂度达到了 O(2^n)\n",
    "\n",
    "我们换个思路，放弃递归，直接从头循环直到算到所需要的项\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibonacci(k):\n",
    "    prev1,prev2=1,1\n",
    "    for _ in range(k-2):\n",
    "        prev1,prev2=prev2,prev1+prev2\n",
    "    return prev2\n",
    "\n",
    "k=int(input())\n",
    "print(fibonacci(k))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "或者，我们也可以把 prev1,prev2 放到参数里"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibonacci(k,prev1=1,prev2=1):\n",
    "    if k<3:\n",
    "        return prev2\n",
    "    return fibonacci(k-1,prev2,prev1+prev2)\n",
    "\n",
    "k=int(input())\n",
    "print(fibonacci(k))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "同样是函数递归，为什么这个代码就没有超时\n",
    "\n",
    "是因为这个函数的递归函数调用只在最后返回的这一步，而解释器会优化掉这个函数调用，直接用子函数覆盖掉原来的位置，而不是重复压入栈中最后再弹出，因此不需要反复计算\n",
    "\n",
    "而一开始的递归函数，最后一步是先调用了两个函数，再将两个函数相加，再返回，因此没有得到函数的值之前就需要压入栈中，所以无法被优化\n",
    "\n",
    "这种只在最后返回调用的递归称为尾递归"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 036:求阶乘的和\n",
    "\n",
    "描述:\n",
    "给定正整数n，求不大于n的正整数的阶乘的和,（即求1!+2!+3!+...+n!）\n",
    "\n",
    "输入:\n",
    "一个正整数n（1 < n < 12）。\n",
    "\n",
    "输出:\n",
    "不大于n的正整数的阶乘的和。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f,s,n=1,0,int(input())\n",
    "for i in range(1,n+1):\n",
    "    f*=i\n",
    "    s+=f\n",
    "print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了避免反复计算阶乘，在计算阶乘的同时就可以累加了"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 037:求不大于n的全部质数\n",
    "\n",
    "描述:\n",
    "求不大于n的全部质数\n",
    "\n",
    "输入:\n",
    "一个正整数n(2<=n<=1000)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "娱乐做法(可跳过,代码风格很差请勿模仿)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[print(x,end=' ') for x in [y for y in range(2,int(input())+1) if all(list(map(lambda z:y%z,range(2,int(y**0.5)+1))))]];"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "淳朴做法：\n",
    "\n",
    "从 2 到 根号 x 依次判断是否能被 x 整除以判断 x 是否是素数，再套一层循环输出 n 以内的素数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isprime(x):\n",
    "    for i in range(2,int(x**0.5)+1):\n",
    "        if not x%i:\n",
    "            return False \n",
    "    return True\n",
    "\n",
    "n=int(input())\n",
    "for i in range(2,n+1):\n",
    "    if isprime(i):\n",
    "        print(i,end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "埃氏筛：\n",
    "\n",
    "上一个做法在判断不同的素数时进行了多次重复运算，我们考虑一下将 n 以内的数建为列表，然后将素数的倍数全部筛去，剩下的就都是素数了"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=int(input())\n",
    "flag=[False]*2+[True]*(n-1)\n",
    "for i in range(2,int(n**0.5)+1):\n",
    "    if flag[i]:\n",
    "        for j in range(2*i,n+1,i):\n",
    "            flag[j]=False\n",
    "for item in range(2,n+1):\n",
    "    if flag[item]:\n",
    "        print(item,end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "欧拉筛：\n",
    "\n",
    "在埃氏筛中，公倍数被重复筛去了，我们考虑一个合数只被它最小的质因数筛去的筛法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=int(input())\n",
    "flag=[False]*2+[True]*(n-1)\n",
    "prime=[]\n",
    "for i in range(2,n+1):\n",
    "    if flag[i]:\n",
    "        prime.append(i)\n",
    "    for j in prime:\n",
    "        if j*i>n:\n",
    "            break\n",
    "        flag[j*i]=False\n",
    "        if not j%i :\n",
    "            break\n",
    "for item in prime:\n",
    "    print(item,end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 038:角古猜想\n",
    "\n",
    "描述:\n",
    "\n",
    "所谓角谷猜想，是指对于任意一个正整数，如果是奇数，则乘3加1，如果是偶数，则除以2，得到的结果再按照上述规则重复处理，最终总能够得到1。如，假定初始整数为5，计算过程分别为16、8、4、2、1。\n",
    "\n",
    "程序要求输入一个整数，将经过处理得到1的过程输出来。\n",
    "\n",
    "输入:\n",
    "一个正整数N(N <= 2,000,000)\n",
    "\n",
    "输出:\n",
    "从输入整数到1的步骤，每一步为一行，每一部中描述计算过程。最后一行输出\"End\"。如果输入为1，直接输出\"End\"。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=int(input())\n",
    "while n>1:\n",
    "    if n%2:\n",
    "        print(f'{n}*3+1={n*3+1}')\n",
    "        n=n*3+1\n",
    "    else:\n",
    "        print(f'{n}/2={n/2:.0f}')\n",
    "        n=n//2\n",
    "print('End')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "没啥好讲的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 039:数字统计\n",
    "\n",
    "描述:\n",
    "请统计某个给定范围[L, R]的所有整数中，数字2出现的次数。\n",
    "\n",
    "比如给定范围[2, 22]，数字2在数2中出现了1次，在数12中出现1次，在数20中出现1次，在数21中出现1次，在数22中出现2次，所以数字2在该范围内一共出现了6次。\n",
    "\n",
    "输入:\n",
    "输入共 1 行，为两个正整数 L 和 R，之间用一个空格隔开。\n",
    "\n",
    "输出:\n",
    "输出共 1 行，表示数字 2 出现的次数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L,R=map(int,input().split())\n",
    "count=0\n",
    "for i in range(L,R+1):\n",
    "    count+=str(i).count('2')\n",
    "print(count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当然先拼成一整个字符串再 count 也是一样的"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L,R=map(int,input().split())\n",
    "st=''\n",
    "for i in range(L,R+1):\n",
    "    st+=str(i)\n",
    "print(st.count('2'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 040:求整数的和与均值\n",
    "\n",
    "描述:\n",
    "读入n（1 <= n <= 10000）个整数，求它们的和与均值。\n",
    "\n",
    "输入:\n",
    "\n",
    "输入第一行是一个整数n，表示有n个整数。\n",
    "\n",
    "第2~n+1行每行包含1个整数。每个整数的绝对值均不超过10000。\n",
    "\n",
    "输出:\n",
    "\n",
    "输出一行，先输出和，再输出平均值（保留到小数点后5位），两个数间用单个空格分隔。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=int(input())\n",
    "lst=[]\n",
    "for _ in range(n):\n",
    "    lst.append(int(input()))\n",
    "print(f'{sum(lst)} {sum(lst)/len(lst):.5f}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "没啥好讲的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 041:整数序列的元素最大跨度值\n",
    "\n",
    "描述:\n",
    "给定一个长度为n的非负整数序列，请计算序列的最大跨度值（最大跨度值 = 最大值减去最小值）。\n",
    "\n",
    "输入:\n",
    "一共2行，第一行为序列的个数n（1 <= n <= 1000)，第二行为序列的n个不超过1000的非负整数，整数之间以一个空格分隔。\n",
    "\n",
    "输出:\n",
    "输出一行，表示序列的最大跨度值。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "input()\n",
    "lst=list(map(int,input().split()))\n",
    "print(max(lst)-min(lst))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "没啥好讲的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 042:毕业生年薪统计\n",
    "\n",
    "描述:\n",
    "有一组毕业生的年薪，请计算其中年薪不少于30万的人数。\n",
    "\n",
    "输入:\n",
    "\n",
    "第一行为一个正整数n，表示学生个数，1<=n<=100。\n",
    "\n",
    "第二行为n个整数，表示n位毕业生的年薪(单位:万元)\n",
    "\n",
    "输出:\n",
    "\n",
    "年薪不少于30万元的人数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "input()\n",
    "lst=list(map(int,input().split()))\n",
    "lst_count=list(map(lambda x:x>=30,lst))\n",
    "print(sum(lst_count))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "将所有人中大于等于 30 的在计数列表中赋值为 1，其他为 0，只要对计数列表求和就可以得到人数\n",
    "\n",
    "当然也可以直接定义一个变量统计"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "input()\n",
    "lst=list(map(int,input().split()))\n",
    "count=0\n",
    "for item in lst:\n",
    "    if item>=30:\n",
    "        count+=1\n",
    "print(count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 043:奥运奖牌计数\n",
    "\n",
    "描述:\n",
    "2008年北京奥运会，A国的运动员参与了n天的决赛项目(1≤n≤17)。现在要统计一下A国所获得的金、银、铜牌数目及总奖牌数。\n",
    "\n",
    "输入:\n",
    "输入n＋1行，第1行是A国参与决赛项目的天数n，其后n行，每一行是该国某一天获得的金、银、铜牌数目，以一个空格分开。\n",
    "\n",
    "输出:\n",
    "输出1行，包括4个整数，为A国所获得的金、银、铜牌总数及总奖牌数，以一个空格分开。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g,s,c=0,0,0\n",
    "n=int(input())\n",
    "for _ in range(n):\n",
    "    dg,ds,dc=map(int,input().split())\n",
    "    g,s,c=g+dg,s+ds,c+dc\n",
    "print(f'{g} {s} {c} {g+s+c}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "没啥好说的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 044:鸡尾酒疗法\n",
    "\n",
    "描述:\n",
    "\n",
    "鸡尾酒疗法，原指“高效抗逆转录病毒治疗”（HAART），由美籍华裔科学家何大一于1996年提出，是通过三种或三种以上的抗病毒药物联合使用来治疗艾 滋病。该疗法的应用可以减少单一用药产生的抗药性，最大限度地抑制病毒的复制，使被破坏的机体免疫功能部分甚至全部恢复，从而延缓病程进展，延长患者生 命，提高生活质量。人们在鸡尾酒疗法的基础上又提出了很多种改进的疗法。为了验证这些治疗方法是否在疗效上比鸡尾酒疗法更好，可用通过临床对照实验的方式 进行。假设鸡尾酒疗法的有效率为x，新疗法的有效率为y，如果y-x大于5%，则效果更好，如果x-y大于5%，则效果更差，否则称为效果差不多。下面给 出n组临床对照实验，其中第一组采用鸡尾酒疗法，其他n-1组为各种不同的改进疗法。请写程序判定各种改进疗法效果如何。\n",
    "\n",
    "输入:\n",
    "\n",
    "第一行为整数n（ 1 < n <= 20）；\n",
    "\n",
    "其余n行每行两个整数，第一个整数是临床实验的总病例数(小于等于10000)，第二个疗效有效的病例数。\n",
    "\n",
    "这n行数据中，第一行为鸡尾酒疗法的数据，其余各行为各种改进疗法的数据。\n",
    "\n",
    "输出:\n",
    "\n",
    "有n-1行输出，分别表示对应改进疗法的效果：\n",
    "\n",
    "如果效果更好，输出better；如果效果更差，输出worse；否则输出same"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=int(input())\n",
    "whole,eff=map(int,input().split())\n",
    "x=eff/whole\n",
    "for _ in range(n-1):\n",
    "    whole,eff=map(int,input().split())\n",
    "    y=eff/whole\n",
    "    if y-x>0.05:\n",
    "        print('better')\n",
    "    elif y-x<-0.05:\n",
    "        print('worse')\n",
    "    else:\n",
    "        print('same')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "没啥好讲的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 045:正常血压\n",
    "\n",
    "描述:\n",
    "\n",
    "监护室每小时测量一次病人的血压，若收缩压在90 - 140之间并且舒张压在60 - 90之间（包含端点值）则称之为正常，现给出某病人若干次测量的血压值，计算病人保持正常血压的最长小时数。\n",
    "\n",
    "输入:\n",
    "\n",
    "第一行为一个正整数n，n < 100\n",
    "\n",
    "其后有n行，每行2个正整数，分别为一次测量的收缩压和舒张压，中间以一个空格分隔。\n",
    "\n",
    "输出:\n",
    "\n",
    "输出仅一行，血压连续正常的最长小时数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=int(input())\n",
    "now,maxlen=0,0\n",
    "for _ in range(n):\n",
    "    h,l=map(int,input().split())\n",
    "    if 90<=h<=140 and 60<=l<=90:\n",
    "        now+=1\n",
    "        if now>maxlen:\n",
    "            maxlen=now\n",
    "    else:\n",
    "        now=0\n",
    "print(maxlen)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "没啥好讲的，now 记录当前连续正常，大于 max 则覆盖 max"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 046:数字反转\n",
    "\n",
    "描述:\n",
    "给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零。\n",
    "\n",
    "输入:\n",
    "输入共 1 行，一个整数N。\n",
    "\n",
    "-1,000,000,000 ≤ N≤ 1,000,000,000。\n",
    "\n",
    "输出:\n",
    "输出共 1 行，一个整数，表示反转后的新数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=input()\n",
    "if n[0]=='-':\n",
    "    print(int(n[0]+n[-1:0:-1]))\n",
    "else:\n",
    "    print(int(n[-1::-1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "没啥好讲的，电脑没电了"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 049:八皇后问题\n",
    "\n",
    "描述:\n",
    "在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。\n",
    "\n",
    "输入:\n",
    "无输入。\n",
    "\n",
    "输出:\n",
    "按给定顺序和格式输出所有八皇后问题的解。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "先试试傻傻地暴力，按行不重来枚举有 8! 种情况"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import permutations\n",
    "\n",
    "lst=list(permutations(range(8)))\n",
    "count=0\n",
    "for item in lst:\n",
    "    chessboard=[[0]*8 for _ in range(8)]\n",
    "    flag=True\n",
    "    for i in range(8):\n",
    "        for j in range(i+1,8):\n",
    "            if abs(i-j)==abs(item[i]-item[j]):\n",
    "                flag=False\n",
    "                break\n",
    "        if not flag:\n",
    "            break\n",
    "    if not flag:\n",
    "        continue\n",
    "    count+=1\n",
    "    for i in range(8):\n",
    "        chessboard[item[i]][i]=1\n",
    "    print(f'No. {count}')\n",
    "    for line in chessboard:\n",
    "        print(*line,sep=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "先用 permutations 求出 0-7 的全排列以表示 0-7 行的皇后所在列\n",
    "\n",
    "再对其依次两两进行斜的判定，即行之间的距离不等于列之间的距离\n",
    "\n",
    "最后得到的结果在棋盘上标记并打印\n",
    "\n",
    "由于枚举了所有行列不重的情况，所以多讨论了很多没必要的分支\n",
    "\n",
    "我们考虑按行依次递推，如果无法满足则回溯到上一行"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "chessboard=[[0]*8 for _ in range(8)]\n",
    "count=0\n",
    "\n",
    "def eightQueen(col):\n",
    "    global count\n",
    "    if col > 7:\n",
    "        count+=1\n",
    "        print(f'No. {count}')\n",
    "        for line in chessboard:\n",
    "            print(*line,sep=' ')\n",
    "        return\n",
    "    \n",
    "    for row in range(8):\n",
    "        if check(row,col):\n",
    "            chessboard[row][col]=1\n",
    "            eightQueen(col+1)\n",
    "            chessboard[row][col]=0\n",
    "\n",
    "def check(row,col):\n",
    "    for line in range(col):\n",
    "        if chessboard[row][line]:\n",
    "            return False\n",
    "\n",
    "        if row-(col-line)>=0 and chessboard[row-(col-line)][line]:\n",
    "            return False\n",
    "\n",
    "        if row+(col-line)<8 and chessboard[row+(col-line)][line]:\n",
    "            return False\n",
    "\n",
    "    return True\n",
    "\n",
    "eightQueen(0) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "eightQueen 函数通过递归来打印出所有答案，通过 global count 计数(要用全局变量)\n",
    "\n",
    "如果当前行满足 check ，就将该位置赋值 1，递归到下一行，直到回溯后归零，若不满足 check 则直接回溯\n",
    "\n",
    "check 的三个 if 分别是判定同一列，主对角线，副对角线是否有重的皇后\n",
    "\n",
    "捎带一提，由于 oj 答案的顺序是按列排序，所以上面所有的解释和代码实际的情况行列是互换的\n",
    "\n",
    "稍微介绍一下二维数组初始化"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a=[[0]*8]*8\n",
    "b=[[0]*8 for _ in range(8)]\n",
    "print(f'a:{a}')\n",
    "print(f'b:{b}')\n",
    "a[0][1]=1\n",
    "b[0][1]=1\n",
    "print(f'a:{a}')\n",
    "print(f'b:{b}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "自行思考两者差别，原因"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 050:上台阶\n",
    "\n",
    "描述:\n",
    "有n级台阶（0<n<20），从下面开始走要走到所有台阶上面，每步可以走一级或两级，问有多少种不同的走法。\n",
    "\n",
    "输入:\n",
    "一个整数n\n",
    "\n",
    "输出:\n",
    "走法总数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def stair(n):\n",
    "    if n<2:\n",
    "        return 1\n",
    "    return stair(n-1)+stair(n-2)\n",
    "\n",
    "n=int(input())\n",
    "print(stair(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "找到递推然后递归，n 级台阶可以是 n-1 走一级或者 n-2 走两级\n",
    "\n",
    "当然也可以用列表保存然后动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 051:汉诺塔问题\n",
    "\n",
    "描述:\n",
    "\n",
    "古代有一个梵塔，塔内有三个座A、B、C，A座上有n个盘子，盘子大小不等，大的在下，小的在上。三个座都可以用来放盘子。有一个和尚想把这n个盘子从A座移到C座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。输入盘子数目n，要求输出移动的步骤。\n",
    "\n",
    "输入:\n",
    "\n",
    "盘子数目n ( n < 8)\n",
    "\n",
    "输出:\n",
    "\n",
    "移动方案"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tower(n,a,b,c):\n",
    "    if n<1:\n",
    "        return \n",
    "    tower(n-1,a,c,b)\n",
    "    print(f'{a}->{c}')\n",
    "    tower(n-1,b,a,c)\n",
    "\n",
    "n=int(input())\n",
    "tower(n,'A','B','C')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果要将 n 个盘子从 A 移到 C,只需要将 n-1 个盘子从 A 移到 B ，再把第 n 个盘子从 A 移到 C ，再把 n-1 个盘子从 B 移到 C\n",
    "\n",
    "依次递归，用参数记录 A B C 的相对位置"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 052:N皇后问题\n",
    "\n",
    "描述:\n",
    "\n",
    "国际象棋的棋盘是由8×8共64个方格构成，棋子放在方格里面。如果两个皇后棋子在同一行、同一列，或者在某个正方形的对角线上，那么这两个皇后就会互相攻击。请在棋盘上摆放8个皇后，使得它们都不会互相攻击。这是经典的8皇后问题。\n",
    "\n",
    "现在要解决N皇后问题：将N个皇后摆放在一个N行N列的国际象棋棋盘上，要求任何两个皇后不能互相攻击。输入皇后数N(1<=N<=9),输出所有的摆法。无解输出\"NO ANSWER\"。行列号都从0开始算。\n",
    "\n",
    "输入:\n",
    "\n",
    "一个整数N，表示要把N个皇后摆放在一个N行N列的国际象棋棋盘上\n",
    "\n",
    "输出:\n",
    "\n",
    "所有的摆放放案。每个方案一行，依次是第0行皇后位置、第1行皇后位置......第N-1行皇后位置。:\n",
    "\n",
    "多种方案输出顺序如下：优先输出第0行皇后列号小的方案。如果两个方案第0行皇后列号一致，那么优先输出第1行皇后列号小的方案......以此类推"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "collist=[]\n",
    "flag=True\n",
    "\n",
    "def nQueen(n,row):\n",
    "    global collist\n",
    "    global flag\n",
    "    if row > n-1:\n",
    "        flag=False\n",
    "        print(*collist,sep=' ')\n",
    "        return\n",
    "    \n",
    "    for col in range(n):\n",
    "        if check(row,col):\n",
    "            collist.append(col)\n",
    "            nQueen(n,row+1)\n",
    "            collist.pop()\n",
    "\n",
    "def check(row,col):\n",
    "    for line in range(row):\n",
    "        if collist[line]==col:\n",
    "            return False\n",
    "\n",
    "        if col-collist[line]==row-line:\n",
    "            return False\n",
    "\n",
    "        if collist[line]-col==row-line:\n",
    "            return False\n",
    "\n",
    "    return True\n",
    "\n",
    "n=int(input())\n",
    "nQueen(n,0)\n",
    "if flag:\n",
    "    print('NO ANSWER')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "将八皇后稍作修改，加上 NO ANSWER 判定即可"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 053:求最大公约数问题\n",
    "\n",
    "描述:\n",
    "给定两个正整数，求它们的最大公约数。\n",
    "\n",
    "输入:\n",
    "输入一行，包含两个正整数(<1,000,000,000)。\n",
    "\n",
    "输出:\n",
    "输出一个正整数，即这两个正整数的最大公约数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gcd(m,n):\n",
    "    if m%n==0:\n",
    "        return n\n",
    "    return gcd(n,m%n)\n",
    "\n",
    "m,n=map(int,input().split())\n",
    "print(gcd(m,n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在 032:求最小公倍数已经写过了，用的辗转相除法\n",
    "\n",
    "假设a > b > 0，那么a和b的最大公约数等于b和a%b的最大公约数，然后把b和a%b作为新一轮的输入。\n",
    "由于这个过程会一直递减，直到a%b等于0的时候，b的值就是所要求的最大公约数。\n",
    "\n",
    "比如：\n",
    "\n",
    "9和6的最大公约数等于6和9%6=3的最大公约数。\n",
    "由于6%3==0，所以最大公约数为3。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 054:递归复习法\n",
    "\n",
    "描述:\n",
    "\n",
    "据说，学渣复习期末考试，要用递归复习法，即当他复习知识点A的时候，他发现理解知识点A必须先理解知识点B和知识点C，于是他先去学习知识点B和知识点C，当他复习知识点B的时候，又发现理解知识点B必须先理解知识点D与知识点E，又得先去复习知识点D和知识点E。\n",
    "\n",
    "现在学渣小明正在通过递归复习法复习知识点n。对任意知识点1 <= k <= n，他复习这个知识点本身需要k小时的时间。但是，小明对这些知识点非常不熟悉，以至于他对任意知识点k， 3 <= k <= n，都必须先复习知识点k - 1和k - 2才能复习知识点k；在复习知识点k - 1的时候，又得先复习知识点k - 2和k - 3才能复习知识点k - 1；以此类推……。注意，即使在复习知识点k - 1的时候他已经复习过了知识点k - 2，在复习知识点k之前他已经忘掉了知识点k - 2，因此他还是会再复习一遍知识点k - 2，并重复上述的递归过程完成新的一轮k - 2的复习后，才会复习知识点k。\n",
    "\n",
    "现在请问他一共需要多少个小时才能完成知识点n的复习？\n",
    "\n",
    "输入:\n",
    "\n",
    "第一行是一个整数m，代表数据组数，1 <= m <= 25\n",
    "\n",
    "之后m行，每行是一组数据，即一个整数n，1 <= n <= 25\n",
    "\n",
    "输出:\n",
    "\n",
    "对每组数据，输出小明复习知识点n所需要的时间"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def review(k):\n",
    "    if k<3:\n",
    "        return k\n",
    "    return k+review(k-1)+review(k-2)\n",
    "\n",
    "n=int(input())\n",
    "for _ in range(n):\n",
    "    k=int(input())\n",
    "    print(review(k))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "按照题目标题给的，直接递归就行了，k-1 k-2 的时间加上 k 即为 k 的时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 055:多少种取法\n",
    "\n",
    "描述:\n",
    "\n",
    "给定三个正整数m,n,s问从1到m这m个数里面取n个不同的数，使它们和是s,有多少种取法\n",
    "\n",
    "输入:\n",
    "\n",
    "多组数据\n",
    "\n",
    "输入的第一行是整数t，表示有t组数据\n",
    "\n",
    "此后有t行，每行是一组数据\n",
    "\n",
    "每组数据就是三个正整数，m,n, s ( n <= 10,s <= 20)\n",
    "\n",
    "输出:\n",
    "\n",
    "对每组数据，输出答案"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def n_sums(m,n,s):\n",
    "    if m<1 or s<1 or n<1:\n",
    "        return 0\n",
    "    if n==1 and s<=m:\n",
    "        return 1\n",
    "    return n_sums(m-1,n,s)+n_sums(m-1,n-1,s-m)\n",
    "\n",
    "t=int(input())\n",
    "for _ in range(t):\n",
    "    m,n,s=map(int,input().split())\n",
    "    print(n_sums(m,n,s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "采用递归，从 1 到 m 中取 n 个数和为 s,那么我们把第 m 去掉，这些和里面有一类是包含 m 的，那么现在就是 1 到 m-1 中取 n-1 个和为 s-m,另一类不包含 m,则是在 1 到 m-1 中取 n 个和为 s 的\n",
    "\n",
    "当 n 为 1 时，若 s 在里面能取到，则返回 1 ，若有一值为负，则返回0\n",
    "\n",
    "当然也可以用 combinations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import combinations\n",
    "\n",
    "t=int(input())\n",
    "for _ in range(t):\n",
    "    m,n,s=map(int,input().split())\n",
    "    cb=list(map(lambda x:sum(x)==s,combinations(range(1,m+1),n)))\n",
    "    print(sum(cb))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "得到 1 到 m 中取 n 个的全部组合，采用 map 映射到 cb，若和为 s 则对应位置为 1 ，反之为 0.那么这些 1 的和就是组合的和为 s 的取法总数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 056:分解因数\n",
    "\n",
    "描述:\n",
    "给出一个正整数a，要求分解成若干个正整数的乘积，即a = a1 * a2 * a3 * ... * an，并且1 < a1 <= a2 <= a3 <= ... <= an，问这样的分解的种数有多少。注意到a = a也是一种分解。\n",
    "\n",
    "输入:\n",
    "第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a (1 < a < 32768)\n",
    "\n",
    "输出:\n",
    "n行，每行输出对应一个输入。输出应是一个正整数，指明满足要求的分解的种数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def resolve(a,b):\n",
    "    global sum\n",
    "    for i in range(b,int(a**0.5)+1):\n",
    "        if not a%i:\n",
    "            sum+=1\n",
    "            resolve(a/i,i)\n",
    "    return \n",
    "\n",
    "n=int(input())\n",
    "for _ in range(n):\n",
    "    sum=1\n",
    "    resolve(int(input()),2)\n",
    "    print(sum)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "和八皇后类似，是递归回溯的应用\n",
    "\n",
    "我们考虑一个整数 a，从 b 开始枚举，若为它的因数 i,则得到一组分解 a=i*(a/i)\n",
    "\n",
    "之后考虑 a/i 的分解 a/i=$\\Pi$,则每有一组分解，原 a 也得到一组分解 a=i*$\\Pi$ \n",
    "\n",
    "直到枚举到根号 a(防止重复)，则返回上一级\n",
    "\n",
    "同时用 b 记录当前已经递归到的最小因数，避免重复计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 057:全排列\n",
    "\n",
    "描述:\n",
    "\n",
    "给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。 我们假设对于小写字母有'a' < 'b' < ... < 'y' < 'z'，而且给定的字符串中的字母已经按照从小到大的顺序排列。\n",
    "\n",
    "输入:\n",
    "\n",
    "输入只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在1到6之间。\n",
    "\n",
    "输出:\n",
    "\n",
    "输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义：\n",
    "\n",
    "已知S = s1s2...sk , T = t1t2...tk，则S < T 等价于，存在p (1 <= p <= k)，使得s1 = t1, s2 = t2, ..., s(p - 1) = t(p - 1), sp < tp成立。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def A(s):\n",
    "    if len(s)==1:\n",
    "        return [s] \n",
    "    lst=[]\n",
    "    for ch in s:\n",
    "        for string in A(s.replace(ch,'')):\n",
    "            lst.append(ch+string)\n",
    "    return lst\n",
    "\n",
    "s=input()\n",
    "s=''.join(sorted(s))\n",
    "print(*A(s),sep='\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "字母序依次提取出一个字符，和递归后得到的字符列表拼接，即字符串的全排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 058:校门外的树\n",
    "\n",
    "描述:\n",
    "\n",
    "某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。\n",
    "\n",
    "马路上有一些区域要用来建地铁，这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。\n",
    "\n",
    "输入:\n",
    "\n",
    "输入的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。\n",
    "\n",
    "输出:\n",
    "\n",
    "输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "L,M=map(int,input().split())\n",
    "road=[1]*(L+1)\n",
    "for _ in range(M):\n",
    "    l,r=map(int,input().split())\n",
    "    for index in range(l,r+1):\n",
    "        road[index]=0\n",
    "print(sum(road))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "用 road 标记道路，列表元素值为 1 即该区域有树\n",
    "\n",
    "循环读入地铁区域把 road 值赋为 0 ，求和即为剩余的树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 059:石头剪刀布\n",
    "\n",
    "描述:\n",
    "\n",
    "石头剪刀布是常见的猜拳游戏。石头胜剪刀，剪刀胜布，布胜石头。如果两个人出拳一样，则不分胜负。\n",
    "\n",
    "一天，小A和小B正好在玩石头剪刀布。已知他们的出拳都是有周期性规律的，比如：“石头-布-石头-剪刀-石头-布-石头-剪刀……”，就是以“石头-布-石头-剪刀”为周期不断循环的。请问，小A和小B比了N轮之后，谁赢的轮数多？\n",
    "\n",
    "输入:\n",
    "\n",
    "输入包含三行。\n",
    "\n",
    "第一行包含三个整数：N，NA，NB，分别表示比了N轮，小A出拳的周期长度，小B出拳的周期长度。0 < N,NA,NB < 100。\n",
    "\n",
    "第二行包含NA个整数，表示小A出拳的规律。\n",
    "\n",
    "第三行包含NB个整数，表示小B出拳的规律。\n",
    "\n",
    "其中，0表示“石头”，2表示“剪刀”，5表示“布”。相邻两个整数之间用单个空格隔开。\n",
    "\n",
    "输出:\n",
    "\n",
    "输出一行，如果小A赢的轮数多，输出A；如果小B赢的轮数多，输出B；如果两人打平，输出draw。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "awin=[[0,2],[2,5],[5,0]]\n",
    "score=0\n",
    "N,NA,NB=map(int,input().split())\n",
    "a=list(map(int,input().split()))\n",
    "b=list(map(int,input().split()))\n",
    "for index in range(N):\n",
    "    game=[a[index%NA],b[index%NB]]\n",
    "    if game in awin:\n",
    "        score+=1\n",
    "    elif game[0]!=game[1]:\n",
    "        score-=1\n",
    "if score>0:\n",
    "    print('A')\n",
    "elif score<0:\n",
    "    print('B')\n",
    "else:\n",
    "    print('draw')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "用二元列表表示 A,B 的出拳情况，A 胜的情况只有 `[0,2] [2,5] [5,0]` 三种情况，若相等则平局，否则 B 胜\n",
    "\n",
    "index 除以 A(B) 的余数即为对应所出的索引\n",
    "\n",
    "得到出拳情况，若在 A 胜列表内则计分 +1，否则若两者不相等则积分 -1\n",
    "\n",
    "最后为正则 A 胜，为负 B 胜，否则平局"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 060:学生排序\n",
    "\n",
    "描述:\n",
    "对班里的所有学生，先按年龄从大到小排序，年龄相同的按成绩从高到低排，成绩相同的，按姓名从小到大排。\n",
    "\n",
    "输入:\n",
    "第一行为整数n，之后每行为姓名，成绩，年龄\n",
    "\n",
    "输出:\n",
    "将排序的结果输出，每行一个学生，格式和输入格式一样。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "stus=[]\n",
    "n=int(input())\n",
    "for _ in range(n):\n",
    "    name,score,age=input().split()\n",
    "    stus.append([name,int(score),int(age)])\n",
    "stus.sort(key=lambda x:(-x[2],-x[1],x[0]))\n",
    "for stu in stus:\n",
    "    print(f'{stu[0]} {stu[1]} {stu[2]}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从数据结构的角度，这里采用嵌套字典比较合适，但是为了 oj 方便，仅满足做题需要，我就用了列表，实际存储的时候可以用以下形式\n",
    "\n",
    "`{'Kitty':{'score':56,'age':22}}`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 061:图像模糊处理\n",
    "\n",
    "描述:\n",
    "\n",
    "给定n行m列的图像各像素点的灰度值，要求用如下方法对其进行模糊化处理：\n",
    "\n",
    "1. 四周最外侧的像素点灰度值不变；\n",
    "\n",
    "2. 中间各像素点新灰度值为该像素点及其上下左右相邻四个像素点原灰度值的平均（舍入到最接近的整数）。\n",
    "\n",
    "输入:\n",
    "\n",
    "第一行包含两个整数n和m，表示图像包含像素点的行数和列数。1 <= n <= 100，1 <= m <= 100。\n",
    "\n",
    "接下来n行，每行m个整数，表示图像的每个像素点灰度。相邻两个整数之间用单个空格隔开，每个元素均在0~255之间。\n",
    "\n",
    "输出:\n",
    "\n",
    "n行，每行m个整数，为模糊处理后的图像。相邻两个整数之间用单个空格隔开。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n,m=map(int,input().split())\n",
    "a,b=[],[[0]*m for _ in range(n)]\n",
    "for _ in range(n):\n",
    "    a.append(list(map(int,input().split())))\n",
    "for i in range(n):\n",
    "    for j in range(m):\n",
    "        if i == 0 or j == 0 or i == n-1 or j == m-1:\n",
    "            b[i][j]=a[i][j]\n",
    "        else:\n",
    "            b[i][j]=round((a[i-1][j]+a[i][j-1]+a[i][j+1]+a[i+1][j]+a[i][j])/5)\n",
    "for line in b:\n",
    "    print(*line,sep=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "二维数组的运用，关于二维数组创建的注意事项在八皇后已经提到了"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 062:单词出现频率统计\n",
    "\n",
    "描述:\n",
    "统计单词出现次数并排序输出\n",
    "\n",
    "输入:\n",
    "最多60,000个单词，每个一行。单词由小写字母构成，不超过30个字符。\n",
    "\n",
    "输出:\n",
    "按单词出现次数从高到低输出所有单词。次数相同的，按照词典序从小到大排。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dic={}\n",
    "while True:\n",
    "    try:\n",
    "        word=input()\n",
    "        dic[word]=dic.get(word,0)+1\n",
    "    except:\n",
    "        break\n",
    "lst=sorted(dic.items(),key=lambda x:(-x[1],x[0]))\n",
    "for i in lst:\n",
    "    print(f'{i[1]} {i[0]}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "034:求最大整数中提到的异常处理输入和字典的综合运用"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 063:统计不重复的单词个数\n",
    "\n",
    "描述:\n",
    "输入不超过60,000个单词，每行一个，统计不重复的单词一共有多少个。单词由小写字母构成，长度不超过30。\n",
    "\n",
    "输入:\n",
    "若干单词\n",
    "\n",
    "输出:\n",
    "不重复单词个数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "st=set()\n",
    "while True:\n",
    "    try:\n",
    "        word=input()\n",
    "        st.add(word)\n",
    "    except:\n",
    "        break\n",
    "print(len(st))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "不重复联想到集合，由于集合的去重功能，只要往内添加最后输出总个数就可以了"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 064:过滤多余的空格\n",
    "\n",
    "描述:\n",
    "一个句子中也许有多个连续空格，过滤掉多余的空格，只留下一个空格。\n",
    "\n",
    "输入:\n",
    "一行，一个字符串（长度不超过200），句子的头和尾都没有空格。\n",
    "\n",
    "输出:\n",
    "过滤之后的句子。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sentence=input()\n",
    "pre=ans=''\n",
    "for i in range(len(sentence)):\n",
    "    if pre!=' ' or sentence[i]!=' ':\n",
    "        ans+=sentence[i]\n",
    "    pre=sentence[i]\n",
    "print(ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "最质朴的做法，字符串依次判定，用 pre 记录前一个字符，如果前一个字符和当前字符有一者不为空格，则将当前字符放入输出字符串\n",
    "\n",
    "当然，也可以用正则"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "print(re.sub(' +',' ',input()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "re 是正则模块，用来进行字符串匹配的相关操作\n",
    "\n",
    "re.sub 是替换操作，第一个参数是匹配的类型，这里用 `' +'` 是指当有1个或以上的空格时匹配，第二个参数是替换的字符串，第三个参数是进行替换操作的原字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 065:统计数字字符个数\n",
    "\n",
    "描述:\n",
    "输入一行字符，统计出其中数字字符的个数。\n",
    "\n",
    "输入:\n",
    "一行字符串，总长度不超过255。\n",
    "\n",
    "输出:\n",
    "输出为1行，输出字符串里面数字字符的个数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "lst=re.findall('\\d',input())\n",
    "print(len(lst))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`'\\d'` 匹配数字字符，findall 寻找字符串中所有匹配的模式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 066:大小写字符互换\n",
    "\n",
    "描述:\n",
    "把一个字符串中所有出现的大写字母都替换成小写字母，同时把小写字母替换成大写字母。\n",
    "\n",
    "输入:\n",
    "输入一行：待互换的字符串。\n",
    "\n",
    "输出:\n",
    "输出一行：完成互换的字符串（字符串长度小于80）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(input().swapcase())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "有内置方法了。。。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "swap=lambda x:x.group().upper() if 'a'<=x.group()<='z' else x.group().lower()\n",
    "\n",
    "print(re.sub('[a-zA-Z]',swap,input()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "用正则尝试一下，sub 也可以用函数来替换，但是注意匹配的是 match 类型，要用 group 方法转成字符串再操作"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 067:找第一个只出现一次的字符\n",
    "\n",
    "描述:\n",
    "给定一个只包含小写字母的字符串，请你找到第一个仅出现一次的字符。如果没有，输出no。\n",
    "\n",
    "输入:\n",
    "一个字符串，长度小于100000。\n",
    "\n",
    "输出:\n",
    "输出第一个仅出现一次的字符，若没有则输出no。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find1(s):\n",
    "    for ch in s:\n",
    "        if s.count(ch)==1:\n",
    "            return ch\n",
    "    return 'no'\n",
    "\n",
    "s=input()\n",
    "print(find1(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "利用了 count 方法，如果计数为 1 则返回该字符，否则返回 'no'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 068:判断字符串是否为回文\n",
    "\n",
    "描述:\n",
    "输入一个字符串，输出该字符串是否回文。回文是指顺读和倒读都一样的字符串。\n",
    "\n",
    "输入:\n",
    "输入为一行字符串（字符串中没有空白字符，字符串长度不超过100）。\n",
    "\n",
    "输出:\n",
    "如果字符串是回文，输出yes；否则，输出no。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s=input()\n",
    "print('yes' if s==s[::-1] else 'no')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "倒着切个片"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 069:字符串最大跨距\n",
    "\n",
    "描述:\n",
    "\n",
    "有三个字符串S,S1,S2，其中，S长度不超过300，S1和S2的长度不超过10。想检测S1和S2是否同时在S中出现，且S1位于S2的左边，并在S中互不交叉（即，S1的右边界点在S2的左边界点的左侧）。计算满足上述条件的最大跨距（即，最大间隔距离：最右边的S2的起始点与最左边的S1的终止点之间的字符数目）。如果没有满足条件的S1，S2存在，则输出-1。\n",
    "\n",
    "例如，S = \"abcd123ab888efghij45ef67kl\", S1=\"ab\", S2=\"ef\"，其中，S1在S中出现了2次，S2也在S中出现了2次，最大跨距为：18。\n",
    "\n",
    "输入:\n",
    "\n",
    "三个串：S, S1, S2，其间以逗号间隔（注意，S, S1, S2中均不含逗号和空格）；\n",
    "\n",
    "输出:\n",
    "\n",
    "S1和S2在S最大跨距；若在S中没有满足条件的S1和S2，则输出-1。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s,s1,s2=input().split(',')\n",
    "s1t=s.find(s1)+len(s1)-1\n",
    "s2h=s.rfind(s2)\n",
    "if s1 in s and s2 in s and s2h>s1t:\n",
    "    print(s2h-s1t-1)\n",
    "else:\n",
    "    print(-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "rfind 与 find 类似，不过 rfind 查找的是最后一个位置"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 070:找出全部子串位置\n",
    "\n",
    "描述:\n",
    "\n",
    "输入两个串s1,s2，找出s2在s1中所有出现的位置\n",
    "\n",
    "两个子串的出现不能重叠。例如'aa'在 aaaa 里出现的位置只有0,2\n",
    "\n",
    "输入:\n",
    "\n",
    "第一行是整数n\n",
    "\n",
    "接下来有n行，每行两个不带空格的字符串s1,s2\n",
    "\n",
    "输出:\n",
    "\n",
    "对每行，从小到大输出s2在s1中所有的出现位置。位置从0开始算\n",
    "\n",
    "如果s2没出现过，输出 \"no\"\n",
    "\n",
    "行末多输出空格没关系"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = int(input())\n",
    "for i in range(n):\n",
    "    s1,s2 =input().split()\n",
    "    temp = 0\n",
    "    while s1.find(s2,temp) != -1 :\n",
    "        temp = s1.find(s2,temp)\n",
    "        print(temp,end = ' ') \n",
    "        temp += len(s2)\n",
    "    if temp == 0 :\n",
    "        print(\"no\")\n",
    "    else :\n",
    "        print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "依次 find ,并用 temp 记录目前 find 到的位置"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "n=int(input())\n",
    "for _ in range(n):\n",
    "    s1,s2=input().split()\n",
    "    if s2 not in s1:\n",
    "        print('no')\n",
    "        continue\n",
    "    ite=re.finditer(s2,s1)\n",
    "    for i in ite:\n",
    "        print(i.span()[0],end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "利用正则的 finditer 可以找到所有匹配的子串并且存入迭代器中，依次提取即可"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 071\n",
    "\n",
    "和 059 貌似一模一样？？？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 072:向量点积计算\n",
    "\n",
    "描述:\n",
    "\n",
    "在线性代数、计算几何中，向量点积是一种十分重要的运算。\n",
    "\n",
    "给定两个n维向量a=(a1,a2,...,an)和b=(b1,b2,...,bn)，求点积a·b=a1b1+a2b2+...+anbn。\n",
    "\n",
    "输入:\n",
    "\n",
    "第一行是一个整数n。1 <= n <= 1000。\n",
    "\n",
    "第二行包含n个整数a1,a2,...,an。\n",
    "\n",
    "第三行包含n个整数b1,b2,...,bn。\n",
    "\n",
    "相邻整数之间用单个空格隔开。每个整数的绝对值都不超过1000。\n",
    "\n",
    "输出:\n",
    "\n",
    "一个整数，即两个向量的点积结果。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "input()\n",
    "a=map(int,input().split())\n",
    "b=map(int,input().split())\n",
    "print(sum(i*j for i,j in zip(a,b)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "向量运算感觉用 numpy 更好算，但 oj 应该没有\n",
    "\n",
    "这里用 zip 把 a,b 拼接，然后生成式内积求和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 073:万年历\n",
    "\n",
    "描述:\n",
    "\n",
    "给定年月日，求星期几。已知2020年11月18日是星期三。另外，本题有公元0年，这个和真实的纪年不一样\n",
    "\n",
    "输入:\n",
    "\n",
    "第一行是n(n <=30)，表示有n组数据\n",
    "\n",
    "接下来n行，每行是一组数据。\n",
    "\n",
    "每行三个整数y,m,d，分别代表年，月，日。(-1000000<=y<=1000000)\n",
    "\n",
    "若今年是2017年，则往前就是2016年，2015年....一直数到2年，1年，再往前就是0年，-1年，-2年.....\n",
    "\n",
    "输出:\n",
    "\n",
    "对每组数据，输出星期几，星期几分别用\n",
    "\n",
    "\"Sunday\",\"Monday\",\"Tuesday\",\"Wednesday\",\"Thursday\", \"Friday\",\"Saturday\" 表示\n",
    "\n",
    "如果月份和日期不合法，输出\"Illegal\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "isleap=lambda y:y%400==0 or (y%4==0 and y%100>0)\n",
    "days=[[31,28,31,30,31,30,31,31,30,31,30,31],[31,29,31,30,31,30,31,31,30,31,30,31]]\n",
    "lst=['Sunday','Monday','Tuesday','Wednesday','Thursday','Friday','Saturday']\n",
    "\n",
    "def c2d(y,m,d):\n",
    "    sum=0\n",
    "    if y>0:\n",
    "        for i in range(y):\n",
    "            sum+=(366 if isleap(i) else 365)\n",
    "    else:\n",
    "        for i in range(y,0):\n",
    "            sum-=(366 if isleap(i) else 365)\n",
    "    for i in range(m-1):\n",
    "        sum+=days[isleap(y)][i] \n",
    "    sum+=d\n",
    "    return sum\n",
    "\n",
    "n=int(input())\n",
    "ref=c2d(2020,11,18)\n",
    "for _ in range(n):\n",
    "    y,m,d=map(int,input().split())\n",
    "    if 0<m<=12 and 0<d<=days[isleap(y)][m-1]: \n",
    "        index=(3+c2d(y,m,d)-ref)%7\n",
    "        print(lst[index])\n",
    "    else:\n",
    "        print('Illegal')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一个相对比较综合的偏应用处理的题目\n",
    "\n",
    "如果不是范围较大且设置了公元0年，实际上可以用日期和时间模块，但这里就不介绍了\n",
    "\n",
    "首先定义判断闰年函数，设置各个月份相对的天数列表，0 为非闰，1 为闰\n",
    "\n",
    "定义星期几的列表\n",
    "\n",
    "定义 c2d 函数，参数为年月日，功能为这个日期相对于 0,0,0 的天数\n",
    "\n",
    "首先讨论年份正负，累加(减)对应的天数，闰年366，非闰365\n",
    "\n",
    "然后累加对应年数月份天数，days[isleap(y)][i]\n",
    "\n",
    "最后加上对应天数\n",
    "\n",
    "计算实际星期的时候只需要与参考值 2020,11,18 的 c2d 相减，对7取模，加上参考的星期三再到对应列表索引就可以了"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 074:很简单的整数划分问题\n",
    "\n",
    "描述:\n",
    "\n",
    "将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。\n",
    "\n",
    "正整数n 的这种表示称为正整数n 的划分。正整数n 的不同的划分个数称为正整数n 的划分数\n",
    "\n",
    "输入:\n",
    "\n",
    "一个整数N(0 < N <= 30)。\n",
    "\n",
    "输出:\n",
    "\n",
    "输出N的划分数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(n,m):\n",
    "    sum=0 \n",
    "    if m==1:\n",
    "        return 1\n",
    "    for i in range(n//m+1):\n",
    "        sum+=f(n-m*i,m-1)\n",
    "    return sum\n",
    "\n",
    "N=int(input())\n",
    "print(f(N,N))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们考虑将整数 n 划分为若干个最大为 m 的整数\n",
    "\n",
    "当 m 为 1 时，只有一种划分法\n",
    "\n",
    "否则，依次累加 1 个 m ,2 个 m ...(n//m) 个 m，剩下的数划分为最大为 m-1 的划分数\n",
    "\n",
    "最后考虑 f(n,n) 即可得到整数的划分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 075:病人排队\n",
    "\n",
    "描述:\n",
    "\n",
    "病人登记看病，编写一个程序，将登记的病人按照以下原则排出看病的先后顺序：\n",
    "\n",
    "1. 老年人（年龄 >= 60岁）比非老年人优先看病。\n",
    "\n",
    "2. 老年人按年龄从大到小的顺序看病，年龄相同的按登记的先后顺序排序。\n",
    "\n",
    "3. 非老年人按登记的先后顺序看病。\n",
    "\n",
    "输入:\n",
    "\n",
    "第1行，输入一个小于100的正整数，表示病人的个数；\n",
    "\n",
    "后面按照病人登记的先后顺序，每行输入一个病人的信息，包括：一个长度小于10的字符串表示病人的ID（每个病人的ID各不相同且只含数字和字母），一个整数表示病人的年龄，中间用单个空格隔开。\n",
    "\n",
    "输出:\n",
    "\n",
    "按排好的看病顺序输出病人的ID，每行一个。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "old={}\n",
    "young={}\n",
    "n=int(input())\n",
    "for _ in range(n):\n",
    "    id,age=input().split()\n",
    "    age=int(age)\n",
    "    if age>=60:\n",
    "        old[id]=age\n",
    "    else:\n",
    "        young[id]=age\n",
    "ptt=sorted(old.items(),key=lambda x:-x[1])\n",
    "ptt.extend(young.items())\n",
    "for p in ptt:\n",
    "    print(p[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "将老年人和非老年人按字典分开记录，将老年人按年龄倒序排序，再拼接后输出"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 076:回文子串\n",
    "\n",
    "描述:\n",
    "\n",
    "给定一个字符串，输出所有长度至少为2的回文子串。\n",
    "\n",
    "回文子串即从左往右输出和从右往左输出结果是一样的字符串，比如：abba，cccdeedccc都是回文字符串。\n",
    "\n",
    "输入:\n",
    "\n",
    "一个字符串，由字母或数字组成。长度500以内。\n",
    "\n",
    "输出:\n",
    "\n",
    "输出所有的回文子串，每个子串一行。\n",
    "\n",
    "子串长度小的优先输出，若长度相等，则出现位置靠左的优先输出。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "isrs=lambda s:s==s[::-1]\n",
    "s=input()\n",
    "for l in range(2,len(s)+1):\n",
    "    for index in range(len(s)-l+1):\n",
    "        if isrs(s[index:index+l]):\n",
    "            print(s[index:index+l])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "按长度从 2 到 len(s) 枚举，起始位置从左至右遍历"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 077:矩阵乘法\n",
    "\n",
    "描述:\n",
    "\n",
    "计算两个矩阵的乘法。n\\*m阶的矩阵A乘以m\\*k阶的矩阵B得到的矩阵C 是n\\*k阶的，且C[i][j] = A[i][0]\\*B[0][j] + A[i][1]\\*B[1][j] + …… +A[i][m-1]\\*B[m-1][j](C[i][j]表示C矩阵中第i行第j列元素)。\n",
    "\n",
    "输入:\n",
    "\n",
    "第一行为n, m, k，表示A矩阵是n行m列，B矩阵是m行k列，n, m, k均小于100\n",
    "\n",
    "然后先后输入A和B两个矩阵，A矩阵n行m列，B矩阵m行k列，矩阵中每个元素的绝对值不会大于1000。\n",
    "\n",
    "输出:\n",
    "\n",
    "输出矩阵C，一共n行，每行k个整数，整数之间以一个空格分开。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inmat(M,row):\n",
    "    for i in range(row):\n",
    "        M.append(list(map(int,input().split())))\n",
    "\n",
    "n,m,k=map(int,input().split())\n",
    "A,B=[],[]\n",
    "C=[[0]*k for _ in range(n)]\n",
    "inmat(A,n)\n",
    "inmat(B,m)\n",
    "for i in range(n):\n",
    "    for j in range(k):\n",
    "        C[i][j]=sum(A[i][t]*B[t][j] for t in range(m))\n",
    "for row in C:\n",
    "    print(*row,sep=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义了一个矩阵的输入函数 inmat, 此外就是二维数组的常规操作，实际运用的时候可以考虑用 numpy 模块"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 078:矩阵转置\n",
    "\n",
    "描述:\n",
    "\n",
    "输入一个n行m列的矩阵A，输出它的转置AT。\n",
    "\n",
    "输入:\n",
    "\n",
    "第一行包含两个整数n和m，表示矩阵A的行数和列数。1 <= n <= 100，1 <= m <= 100。\n",
    "\n",
    "接下来n行，每行m个整数，表示矩阵A的元素。相邻两个整数之间用单个空格隔开，每个元素均在1~1000之间。\n",
    "\n",
    "输出:\n",
    "\n",
    "m行，每行n个整数，为矩阵A的转置。相邻两个整数之间用单个空格隔开。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inmat(M,row):\n",
    "    for i in range(row):\n",
    "        M.append(list(map(int,input().split())))\n",
    "\n",
    "n,m=map(int,input().split())\n",
    "A=[]\n",
    "inmat(A,n)\n",
    "for j in range(m):\n",
    "    for i in range(n):\n",
    "        print(A[i][j],end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "偷懒复用了上一题的输入函数，转置输出的话行列遍历顺序换一下就行了"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 079:计算鞍点\n",
    "\n",
    "描述:\n",
    "\n",
    "给定一个5*5的矩阵，每行只有一个最大值，每列只有一个最小值，寻找这个矩阵的鞍点。\n",
    "\n",
    "鞍点指的是矩阵中的一个元素，它是所在行的最大值，并且是所在列的最小值。\n",
    "\n",
    "例如：在下面的例子中（第4行第1列的元素就是鞍点，值为8 ）。\n",
    "\n",
    "11 3 5 6 9\n",
    "\n",
    "12 4 7 8 10\n",
    "\n",
    "10 5 6 9 11\n",
    "\n",
    "8 6 4 7 2\n",
    "\n",
    "15 10 11 20 25\n",
    "\n",
    "输入:\n",
    "\n",
    "输入包含一个5行5列的矩阵\n",
    "\n",
    "输出:\n",
    "\n",
    "如果存在鞍点，输出鞍点所在的行、列及其值，如果不存在，输出\"not found\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inmat(M,row):\n",
    "    for i in range(row):\n",
    "        M.append(list(map(int,input().split())))\n",
    "\n",
    "A=[]\n",
    "inmat(A,5)\n",
    "for row in range(5):\n",
    "    col=A[row].index(max(A[row]))\n",
    "    collst=[A[i][col] for i in range(5)]\n",
    "    rmin=collst.index(min(collst))\n",
    "    if rmin==row:\n",
    "        print(row+1,col+1,A[row][col])\n",
    "        break\n",
    "else:\n",
    "    print('not found')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "还是复用了前两题的输入函数\n",
    "\n",
    "先按行遍历，找出每行的最大值，得到其列索引\n",
    "\n",
    "将其对应列生成列表找到其最小值行索引\n",
    "\n",
    "若行索引与当前行相同，则输出该元素,break\n",
    "\n",
    "若循环结束仍未 break，则输出 'not found'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 080:最简单的单词\n",
    "\n",
    "描述:\n",
    "\n",
    "大家一起在学习单词时，会对学习的单词评分，评分越高，单词越难。现在每个人都对10个单词评分，不同的人可能对同一个单词评分，求最简单的单词。\n",
    "\n",
    "最简单的单词必须被评过分。如果单词被多个人评分，它的综合评分是这些评分的平均数，最后求的是综合评分最小的单词。不会出现多个最简单单词。\n",
    "\n",
    "输入:\n",
    "\n",
    "第一行T，表示有T组数据。\n",
    "\n",
    "对于每组数据：\n",
    "\n",
    "第一行N，表示有N个人。\n",
    "\n",
    "接下来输入N*10行，每一行有一个单词，一个整数（表示评分），由空格隔开。\n",
    "\n",
    "输出:\n",
    "\n",
    "对于每组数据，输出最简单的单词"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T=int(input())\n",
    "for _1 in range(T):\n",
    "    N=int(input())\n",
    "    dic={}\n",
    "    for _2 in range(N*10):\n",
    "        w,score=input().split()\n",
    "        score=int(score)\n",
    "        dic[w]=dic.get(w,[])+[score]\n",
    "    lst=sorted(dic.items(),key=lambda x:sum(x[1])/len(x[1]))\n",
    "    print(lst[0][0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "利用字典，每组数据将评分都存入对应的字典内\n",
    "\n",
    "N*10 个评分后对字典进行按平均分排序，输出平均分最小的单词"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 081:校园食宿预订系统\n",
    "\n",
    "描述:\n",
    "\n",
    "某校园为方便学生订餐，推出食堂预定系统。食宿平台会在前一天提供菜单，学生在开饭时间前可订餐。 食堂每天会推出m个菜，每个菜有固定的菜价和总份数，售卖份数不能超过总份数。 假设共有n个学生点餐，每个学生固定点3个菜，当点的菜售罄时, 学生就买不到这个菜了。 请根据学生预定记录，给出食堂总的预定收入 数据满足1 <= n <= 6000，3 <= m <= 6000，单品菜价不大于1000元，每个菜的配额不超过3000\n",
    "\n",
    "输入:\n",
    "\n",
    "第一行两个整数n和m，代表有n个学生订餐，共有m个可选的菜\n",
    "\n",
    "下面m行，每行三个元素，分别是菜名、售价和可提供量，保证菜名不重合，菜价为整数\n",
    "\n",
    "下面n行，每行三个元素，表示这个学生点的三个菜的菜名\n",
    "\n",
    "输出:\n",
    "\n",
    "一个整数，表示食堂的收入"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n,m=map(int,input().split())\n",
    "meals={}\n",
    "Q=0\n",
    "for _ in range(m):\n",
    "    name,price,Qty=input().split()\n",
    "    meals[name]=[int(price),int(Qty)]\n",
    "for _ in range(n):\n",
    "    stu=input().split()\n",
    "    for mel in stu:\n",
    "        if meals[mel][1]>0:\n",
    "            Q+=meals[mel][0]\n",
    "            meals[mel]=[meals[mel][0],meals[mel][1]-1]\n",
    "print(Q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用字典存储对应菜，键为菜名，值为列表，存储价格和剩余数量\n",
    "\n",
    "买菜时如果菜还有剩，则收益加上该菜价格，同时该菜剩余数量-1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 082:更强的卷王查询系统\n",
    "\n",
    "描述:\n",
    "\n",
    "古人云：“开卷有益”。但是，著名的社会学家小明认为内卷是有害的，并且他正在写一篇与P大内卷现状有关的论文，需要选取具有代表性的“卷王”们进行访谈。小明现在搞到了一份长长的成绩单，拜托你写个程序，帮他找出成绩单上的“卷王”们。\n",
    "\n",
    "“卷王”的定义是：给定一组课程，这组课程全部上过的学生中，这组课程平均分最高的学生。小明已经通过复杂的数据挖掘手段得到了要分析的课程组，现在需要你按照上述定义，对每组课程找出那个真正的“卷王”。\n",
    "\n",
    "输入:\n",
    "\n",
    "第1行：一个整数n， 1 <= n <= 100000\n",
    "\n",
    "第2~(n+1)行：每行有用空格分隔的两个字符串和一个整数，前两个字符串分别代表课程名和学生名，最后一个整数代表这个学生在此课程中取得的成绩。输入保证课程名和学生名只包含字母，且一个学生在一个课程中不会出现两次成绩。输入保证课程数量不超过1000门，且每门课的学生数量不超过100人。输入不保证任何顺序。\n",
    "\n",
    "第n+2行：一个整数m，代表查询的个数，即课程组的组数。1 <= m <= 10\n",
    "\n",
    "接下来m行：每行是一个课程组，第一个整数k代表该组课程的数量，1 <= k <= 100，后面有k个字符串，表示k个课程名。整数k和字符串之间均用一个空格分隔。数据保证课程名一定在之前出现过。\n",
    "\n",
    "输出:\n",
    "\n",
    "输出为m行，每行对应一个课程组，输出该组课程平均分最高的学生，只考虑学过该组全部课程的学生。如果平均分最高的学生多于一个，输出姓名按英文词典排序最靠前的学生。数据保证对每组课程，都存在学过该组所有课程的学生。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "studic={}\n",
    "n=int(input())\n",
    "for _ in range(n):\n",
    "    course,stu,score=input().split()\n",
    "    studic[stu]=studic.get(stu,{})\n",
    "    studic[stu][course]=int(score)\n",
    "n=int(input())\n",
    "for _ in range(n):\n",
    "    lst=input().split()\n",
    "    m=int(lst[0])\n",
    "    cs=lst[1:]\n",
    "    avg={}\n",
    "    for stu in studic:\n",
    "        for course in cs:\n",
    "            if course not in studic[stu]:\n",
    "                break\n",
    "            else:\n",
    "                avg[stu]=avg.get(stu,[])+[studic[stu][course]]\n",
    "        else:\n",
    "            continue\n",
    "    for stu in avg:\n",
    "        if len(avg[stu])<m:\n",
    "            avg[stu]=-1\n",
    "        else:\n",
    "            avg[stu]=sum(avg[stu])/m\n",
    "    avglst=sorted(avg.items(),key=lambda x:(-x[1],x[0]))\n",
    "    print(avglst[0][0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这题可能写的略显凌乱\n",
    "\n",
    "首先考虑把成绩用字典录入，由于每个学生有多门课程，所以采用嵌套字典，外层字典键为学生名，值为内层字典，内层字典键为课程名，值为分数\n",
    "\n",
    "之后对各组课程讨论学生该课程的分数，用字典 avg 保存，键为学生名，值为列表，若学生该课程有分数，则列表里添加此分数\n",
    "\n",
    "添加完后，查看学生添加分数后的课程数，若有课程没成绩则用 -1 标记，否则将列表改写为平均值\n",
    "\n",
    "排序后输出最高分卷王"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 083:抽取ip地址\n",
    "\n",
    "描述:\n",
    "\n",
    "在一段多行的文本中，抽取ip地址。ip地址的左右不能有数字，例如,不能认为'1233.34.44.5'里面包含一个ip地址'233.34.44.5'，也不能认为'233.34.44.525'里面包含一个ip地址'233.34.44.52'。ip地址右边还不能有多余的'.'，比如不能认为'22.22.22.22.33'中包含一个ip地址'22.22.22.33'。假设ip地址不会跨多行。\n",
    "\n",
    "输入:\n",
    "\n",
    "若干行文字\n",
    "\n",
    "输出:\n",
    "\n",
    "文字中的ip地址，每个ip地址一行"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "pattern = re.compile(r'(?<=[^\\d\\.])(?:(?:(?:2[0-4]\\d)|(?:25[0-5])|(?:1\\d{2})|(?:[1-9]?\\d))\\.){3}(?:(?:2[0-4]\\d)|(?:25[0-5])|(?:1\\d{2})|(?:[1-9]?\\d))(?=[^\\d\\.])')\n",
    "s=' '\n",
    "while True:\n",
    "    try:\n",
    "        s=s+input()+' '\n",
    "    except:\n",
    "        break\n",
    "print(*re.findall(pattern,s),sep='\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "正则表达式， ip 地址需要是 a.b.c.d 的形式，a,b,c,d 都小于 256，从本题要求来看不允许前导 0，实际上是可以的\n",
    "\n",
    "先讨论百位 2，那么十位是 0-4 时个位可以为任意数，为 5 时个位小于 6\n",
    "\n",
    "百位 1 ，则十位个位可以是任意数\n",
    "\n",
    "无百位，则十位为 1-9 或不存在十位，个位任意数\n",
    "\n",
    "将这个模式后加小数点，重复三次，再加上这个模式，即为 ip 地址\n",
    "\n",
    "前后不能为数或小数点，因此用零宽断言排除\n",
    "\n",
    "findall 会匹配捕获分组，所以每个分组（小括号）需要用 ?: 调整成非捕获分组\n",
    "\n",
    "输入采用异常处理，同时用空格分隔各行，防止前一行末尾为数或小数点导致不被匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 084:找出所有整数\n",
    "\n",
    "描述\n",
    "给一段文字，可能有中文，把里面的所有非负整数都找出来，不需要去掉前导0。如果碰到 \"012.34\"这样的就应该找出两个整数 012和34,碰到 0.050,就找出 0和050\n",
    "\n",
    "```\n",
    "import re\n",
    "// 在此处补充你的代码\n",
    "while True:\n",
    "    try:\n",
    "        s = input()\n",
    "        lst = re.findall(m,s)\n",
    "        for x in lst:\n",
    "            print(x)\n",
    "    except:\n",
    "        break\n",
    "```\n",
    "\n",
    "输入:\n",
    "一段文字\n",
    "\n",
    "输出:\n",
    "按顺序输出所有整数，每个整数一行"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "m=re.compile(r'\\d+')\n",
    "while True:\n",
    "    try:\n",
    "        s = input()\n",
    "        lst = re.findall(m,s)\n",
    "        for x in lst:\n",
    "            print(x)\n",
    "    except:\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "和上一题比起来就显得很单纯了"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 085:找出所有整数和小数\n",
    "\n",
    "描述\n",
    "给一段文字，可能有中文，把里面的所有非负整数和小数找出来，不需要去掉前导0或小数点后面多余的0， 然后依次输出\n",
    "```\n",
    "import re\n",
    "// 在此处补充你的代码\n",
    "while True:\n",
    "    try:\n",
    "        s = input()\n",
    "        lst = re.findall(m,s)\n",
    "        for x in lst:\n",
    "            print(x)\n",
    "    except:\n",
    "        break\n",
    "```\n",
    "\n",
    "输入:\n",
    "一段文字\n",
    "\n",
    "输出:\n",
    "按顺序输出所有整数和小数，每个整数一行"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "m=re.compile(r'\\d+\\.\\d+|\\d+')\n",
    "while True:\n",
    "    try:\n",
    "        s = input()\n",
    "        lst = re.findall(m,s)\n",
    "        for x in lst:\n",
    "            print(x)\n",
    "    except:\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 086:找出小于100的整数\n",
    "\n",
    "描述\n",
    "有给定的两行输入，在每一行的输入中提取在[0,100)内的整数(不包括100)并依次输出。注意要排除负数\n",
    "```\n",
    "import re\n",
    "m = r\"(^|[^0-9-])(\\d{1,2})([^0-9]|$)\"\n",
    "for i in range(2):\n",
    "        s = input()\n",
    "        lst = re.findall(m,s)\n",
    "        for x in lst:\n",
    "// 在此处补充你的代码\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "m = r\"(^|[^0-9-])(\\d{1,2})([^0-9]|$)\"\n",
    "for i in range(2):\n",
    "        s = input()\n",
    "        lst = re.findall(m,s)\n",
    "        for x in lst:\n",
    "            print(x[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在 ip 那题提到过的 findall 和捕获分组的关系，findall 会把所有捕获分组去分开匹配，最后拼接起来成一个元组，本题中第一个分组保证前不为数字和符号，第三个分组保证后一位不为数，中间分组即所求少于 100 整数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 087:密码判断\n",
    "\n",
    "描述:\n",
    "\n",
    "用户密码的格式是：\n",
    "\n",
    "1) 以大写或小写字母开头\n",
    "\n",
    "2) 至少要有8个字符，最长不限\n",
    "\n",
    "3) 由字母、数字、下划线或 '-' 组成 \n",
    "\n",
    "输入若干字符串，判断是不是符合密码的条件。如果是，输出 yes 如果不是，输出 no\n",
    "```\n",
    "import re\n",
    "// 在此处补充你的代码\n",
    "while True:\n",
    "    try:\n",
    "        s = input()\n",
    "        if re.match(m,s) != None:\n",
    "            print(\"yes\")\n",
    "        else:\n",
    "            print(\"no\")\n",
    "    except:\n",
    "        break\n",
    "```\n",
    "输入:\n",
    "\n",
    "若干行\n",
    "\n",
    "输出:\n",
    "\n",
    "对每行输入，判断其是否符合密码格式，相应地输出 yes 或no"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "m=re.compile(r'^[a-zA-Z][\\da-zA-Z_-]{7,}$')\n",
    "while True:\n",
    "    try:\n",
    "        s = input()\n",
    "        if re.match(m,s) != None:\n",
    "            print(\"yes\")\n",
    "        else:\n",
    "            print(\"no\")\n",
    "    except:\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注意表示开头的 ^ 和表示结尾的 $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 088:找<>中的数\n",
    "\n",
    "描述:\n",
    "\n",
    "输入一串字符，将输入中的，在<>里面的，没有前导0的少于4位的整数依次输出。单独的0也要输出。\n",
    "\n",
    "输入:\n",
    "\n",
    "第一行是整数n，表示后面一共有n个字符串\n",
    "\n",
    "接下来有n行字符串\n",
    "\n",
    "输出:\n",
    "\n",
    "对每个字符串，输出题目要求的结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "m=re.compile(r'(<)(0|[1-9]\\d{0,2})(>)')\n",
    "n=int(input())\n",
    "for _ in range(n):\n",
    "    s=input()\n",
    "    lst=re.findall(m,s)\n",
    "    if len(lst)==0:\n",
    "        print('NONE')\n",
    "        continue\n",
    "    for x in lst:\n",
    "        print(x[1],end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这次用了捕获分组，也可以通过零宽断言和非捕获分组来进行匹配"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "m=re.compile(r'(?<=<)(?:0|[1-9]\\d{0,2})(?=>)')\n",
    "n=int(input())\n",
    "for _ in range(n):\n",
    "    s=input()\n",
    "    lst=re.findall(m,s)\n",
    "    if len(lst)==0:\n",
    "        print('NONE')\n",
    "        continue\n",
    "    print(*lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 089:检查美元\n",
    "\n",
    "描述:\n",
    "\n",
    "给出一句话，判断这句话中是否存在规范书写的美元数纪录。\n",
    "\n",
    "美元数的规范如下：\n",
    "\n",
    "1.以\\$开始,\\$结束。\n",
    "\n",
    "2.数字为整数，从个位起，满3个数字用','分隔\n",
    "\n",
    "正确的格式如：\\$1,023,032\\$ 或者 \\$2\\$\n",
    "\n",
    "错误的格式如：\\$3,432,12\\$ 或者 \\$2\n",
    "\n",
    "输入:\n",
    "\n",
    "若干行\n",
    "\n",
    "输出:\n",
    "\n",
    "对每一行：如果存在规范书写的美元数，输出yes，否则输出no"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "m=re.compile(r'\\$[1-9]\\d{0,2}(,\\d{3})*\\$')\n",
    "while True:\n",
    "    try:\n",
    "        s=input()\n",
    "        if re.search(m,s)!=None:\n",
    "            print('yes')\n",
    "        else:\n",
    "            print('no')\n",
    "    except:\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "将合规的美元划分为最前面的不能有前导零的 1-3 位数，和 *(大于等于0) 个逗号加三位数（可以有前导零），注意美元符号需要转义"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 090:电话号码\n",
    "\n",
    "题目描述用的图片。。。我本来试了一下 ocr ，但是 adobe Acrobat 的 ocr 好像不太行，就给个链接自己去看吧。。。\n",
    "\n",
    "http://cxsjsxmooc.openjudge.cn/book/090/\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "m1=re.compile(r'<([a-z]+)>(.*?)</\\1>')\n",
    "m2=re.compile(r'\\(\\d{1,2}\\)-\\d{3}(?!\\d)')\n",
    "m3=re.compile(r'\\((\\d{1,2})\\)')\n",
    "n=int(input())\n",
    "for _ in range(n):\n",
    "    flag=1\n",
    "    s=input()\n",
    "    lst=re.findall(m1,s)\n",
    "    for x in lst:\n",
    "        if len(re.findall(m2,x[1]))>0:\n",
    "            lst2=re.findall(m2,x[1])\n",
    "            print(f'<{x[0]}>',end='')\n",
    "            lst3=re.findall(m3,''.join(lst2))\n",
    "            print(*lst3,sep=',',end='')\n",
    "            print(f'</{x[0]}>')\n",
    "            flag=0\n",
    "    if flag:\n",
    "        print('NONE')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义了三个正则匹配模式，分别为前后相同 tag,tag 内字符串匹配电话号码，电话号码内匹配括号内区号\n",
    "\n",
    "注意 tag 匹配的时候要用 ? 进行非贪婪\n",
    "\n",
    "第二个和第三个模式应该可以合并，但为了看的清晰一点我就分开写了\n",
    "\n",
    "先对字符串搜索 tag 之间的子串，然后匹配得到电话号码，再匹配得到区号\n",
    "\n",
    "格式化输出 tag 和区号\n",
    "\n",
    "用 flag 标记是否有符合的电话号码，否则输出 'NONE'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 091:通讯记录\n",
    "\n",
    "描述:\n",
    "\n",
    "卜慧娟在邮箱导出通讯记录时，混入了许多乱码符号，她急忙去找计概C学的最好的朋友（你），请求你恢复出她的通讯记录。\n",
    "\n",
    "每条通讯记录都由tag包裹，tag内可能有其他的乱码字符，也可能有多条通讯记录。\n",
    "\n",
    "tag的定义：\n",
    "\n",
    "“\\<X\\>\"和它右边离他最近的\"\\</X\\>\"构成一个tag。tag之间可以有任意字符，X是任意长度不为0的字符串，由字母组成。\n",
    "\n",
    "正确tag如：\\<abv\\>x783b\\</abv\\>\n",
    "\n",
    "下面两行都不是tag：\n",
    "\n",
    "\\<abv\\>jkfg\\</ab\\>\n",
    "\n",
    "\\<\\>jkdg\\</\\>;\n",
    "\n",
    "每条通讯记录的格式为“%内容%邮箱”\n",
    "\n",
    "“内容”部分是任意非空且不包含字符'%'的字符串。\n",
    "\n",
    "“邮箱”部分的格式是：“帐号@pku.edu.cn”或“帐号@stu.pku.edu.cn”\n",
    "\n",
    "帐号是个满足以下两个条件的字符串：\n",
    "\n",
    "1）只包括大小写字母、数字和下划线，不能包含其他特殊字符；\n",
    "\n",
    "2）长度不为0，且不超过8个字符\n",
    "\n",
    "输入:\n",
    "\n",
    "有多组数据，每组数据一行。\n",
    "\n",
    "数据保证不会出现两个tag重叠或嵌套的情况。\n",
    "\n",
    "输出:\n",
    "\n",
    "对每组数据，先输出一行\"----\"，然后再抽取通讯记录输出。每条通讯录记录输出为一行，将内容和邮箱用空格隔开。\n",
    "\n",
    "如果找不到通讯录记录， 则输出NONE （注意字母大小写）。注意，tag外部的文字都不能算通讯记录"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "m1=re.compile(r'<([a-z]+)>(.*?)</\\1>')\n",
    "m2=re.compile(r'%([^%]+)%([a-zA-Z\\d_]{1,8}@(?:pku\\.edu\\.cn|stu\\.pku\\.edu\\.cn))')\n",
    "while True:\n",
    "    try:\n",
    "        flag=1\n",
    "        s=input()\n",
    "        print('----')\n",
    "        lst=re.findall(m1,s)\n",
    "        for x in lst:\n",
    "            lst2=re.findall(m2,x[1])\n",
    "            if len(lst2)>0:\n",
    "                flag=0\n",
    "                for i in lst2:\n",
    "                    print(f'{i[0]} {i[1]}')\n",
    "        if flag:\n",
    "            print('NONE')\n",
    "    except:\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "与上一题类似，不过注意电子邮件中的英文句号需要转义"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 092:时间处理\n",
    "\n",
    "描述:\n",
    "\n",
    "求从给定时刻开始过了给定时间后的时刻。\n",
    "\n",
    "输入:\n",
    "\n",
    "有若干组数据。\n",
    "\n",
    "每组数据有2行，第一行是给定时刻，可能有两种格式\n",
    "\n",
    "格式1) 年 月 日 时 分(时是24小时制)\n",
    "\n",
    "格式2) 月-日-年 时:分 上下午 （时是12小时制,注意没有秒)\n",
    "\n",
    "第二行是时间增量，也可能有两种格式\n",
    "\n",
    "格式1) 一个整数，代表多少秒\n",
    "\n",
    "格式2) 日 时 分\n",
    "\n",
    "输出:\n",
    "\n",
    "对每组数据，输出给定时刻加上时间增量后的新时刻,24小时制\n",
    "\n",
    "格式如： 1982-12-10 12:12:28\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import datetime\n",
    "\n",
    "while True:\n",
    "    try:\n",
    "        s=input()\n",
    "        lst=s.split()\n",
    "        lst2=list(map(int,input().split()))\n",
    "        if len(lst2)==3:\n",
    "            delta=datetime.timedelta(days=lst2[0],hours=lst2[1],minutes=lst2[2])\n",
    "        else:\n",
    "            delta=datetime.timedelta(seconds=lst2[0])\n",
    "        if len(lst)==5:\n",
    "            tm=datetime.datetime.strptime(s,\"%Y %m %d %H %M\")\n",
    "        else:\n",
    "            tm=datetime.datetime.strptime(s,\"%m-%d-%Y %H:%M %p\")\n",
    "        tm2=tm+delta\n",
    "        print(tm2)\n",
    "    except:\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对自带的 datetime 库的考察\n",
    "\n",
    "我通过输入时间的长度来区分时间的格式\n",
    "\n",
    "然后通过 timedelta 方法来定义时间增加量，用 strptime 来按格式输入时间\n",
    "\n",
    "最后输出"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 093:成绩排序\n",
    "\n",
    "描述:\n",
    "给出班里某门课程的成绩单，请你按成绩从高到低对成绩单排序输出，如果有相同分数则名字字典序小的在前。\n",
    "\n",
    "输入:\n",
    "\n",
    "第一行为n (0 < n < 20)，表示班里的学生数目；\n",
    "\n",
    "接下来的n行，每行为每个学生的名字和他的成绩, 中间用单个空格隔开。名字只包含字母且长度不超过20，成绩为一个不大于100的非负整数。\n",
    "\n",
    "输出:\n",
    "\n",
    "把成绩单按分数从高到低的顺序进行排序并输出，每行包含名字和分数两项，之间有一个空格。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n=int(input())\n",
    "score_report={}\n",
    "for _ in range(n):\n",
    "    name,score=input().split()\n",
    "    score=int(score)\n",
    "    score_report[name]=score\n",
    "score_list=sorted(score_report.items(),key=lambda item:(-item[1],item[0]))\n",
    "for item in score_list:\n",
    "    print(f'{item[0]} {item[1]}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "通过字典来记录成绩，键为姓名，值为成绩\n",
    "\n",
    "通过 sorted 函数来对字典的项目排序，注意要通过 items 返回字典的键和值，key 用 lambda 函数定义，先根据成绩倒序，再根据姓名正序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 094:扑克牌排序\n",
    "\n",
    "描述:\n",
    "\n",
    "一副扑克牌有52张牌，分别是红桃，黑桃，方片，梅花各13张，不包含大小王，现在Alex抽到了n张牌，请将扑克牌按照牌面从大到小的顺序排序。\n",
    "\n",
    "牌的表示方法：\n",
    "\n",
    "红桃(heart)用字母h表示\n",
    "\n",
    "黑桃(spade)用字母s表示\n",
    "\n",
    "方片(dianmond)用字母d表示\n",
    "\n",
    "梅花(club)用字母c表示\n",
    "\n",
    "\n",
    "2~10的牌面直接用2,3,4,5,6,7,8,9,10 表示，其余的分别为A，J，Q，K\n",
    "\n",
    "比如方片J用dJ表示， 红桃A用hA表示\n",
    "\n",
    "牌面大小：\n",
    "\n",
    "2>A>K>Q>J>10>9>……>4>3\n",
    "\n",
    "相同牌面的按照花色（h>s>d>c）顺序排。\n",
    "\n",
    "输入:\n",
    "\n",
    "多组数据。每组数据一行，表示当前摸到的n张牌\n",
    "\n",
    "输出:\n",
    "\n",
    "针对每组数据，输出一行，即排序后的结果。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "suit='hsdc'\n",
    "rank=['2','A','K','Q','J','10','9','8','7','6','5','4','3','2','1']\n",
    "\n",
    "while True:\n",
    "    try:\n",
    "        cards=input().split()\n",
    "        print(*sorted(cards,key=lambda x:(rank.index(x[1:]),suit.find(x[0]))))\n",
    "    except:\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "指定顺序的排序\n",
    "\n",
    "我们先设定好有序的列表\n",
    "\n",
    "利用 lambda 函数对需要排序的对我们预先设定的列表取索引，即可实现按要求排序\n"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "a30187288978be1f8e6bd7c2dc03f581ee6232ae2ab099e8954595d92fcb090e"
  },
  "kernelspec": {
   "display_name": "Python 3.9.1 64-bit",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
